#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define ii pair< ll , ll >
#define pb push_back
#define fi first
#define se second
using ll = long long;
constexpr ll LINF = ( 1e18 + 5 );
constexpr ll MAX = 1e6 + 5;
constexpr ll INF = ( 1e9 + 5 );
constexpr int MOD = 1e9 + 7;
template<class X , class Y>
bool maximize( X& x , const Y& y ){
if ( x < y ){
x = y;
return true;
}
return false;
}
template<class X , class Y>
bool minimize( X& x , const Y& y ){
if ( x > y ){
x = y;
return true;
}
return false;
}
template<class T> using MaxHeap = priority_queue< T , vector<T> , less<T> >;
template<class T> using MinHeap = priority_queue< T , vector<T> , greater<T> >;
constexpr ll dx[] = { 0 , 0 , -1 , 1 };
constexpr ll dy[] = { -1 , 1 , 0 , 0 };
const ll L = 2e3 + 5;
char fix[] = { '<' , '>' , '^' , 'v' };
char in[] = { '>' , '<' , 'v' , '^' };
char a[L][L];
ii en , st;
ll n, m;
ll d[L][L];
ii ret[L][L];
bool isValid( ll x , ll y ){
char c = a[x][y];
return x >= 1 && x <= n && y >= 1 && y <= m && c != 'x';
}
void dijkstra( ll rx , ll ry ){
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= m ; j++ ){
d[i][j] = LINF;
ret[i][j] = { -1 , -1 };
}
}
deque<ii> Q;
Q.push_front({ rx, ry });
d[rx][ry] = 0;
while ( !Q.empty() ){
auto [ x , y ] = Q.front();
if ( Q.front() == st ) return;
Q.pop_front();
for ( int i = 0 ; i < 4 ; i++ ){
ll nx = x + dx[i];
ll ny = y + dy[i];
if ( !isValid( nx , ny ) ) continue;
ll cost = 1;
if ( a[nx][ny] == in[i] ) cost = 0;
if ( a[nx][ny] == 'o' ) cost = 0;
if ( d[nx][ny] > d[x][y] + cost ){
d[nx][ny] = d[x][y] + cost;
ret[nx][ny] = { x, y };
if (cost) Q.push_back({ nx , ny });
else Q.push_front({ nx , ny });
}
}
}
}
void Whisper(){
cin >> n >> m;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= m ; j++ ){
cin >> a[i][j];
if ( a[i][j] == 'o' ){
st = { i , j };
}
if ( a[i][j] == 'x' ){
en = { i , j };
}
}
}
dijkstra( en.fi , en.se );
cout << d[st.fi][st.se] << '\n';
ii cur = st;
while ( cur != en ){
auto [ x , y ] = cur;
ii go = ret[x][y];
for ( int i = 0 ; i < 4 ; i++ ){
int nx = x + dx[i];
int ny = y + dy[i];
if ( nx == go.fi && ny == go.se ){
if ( a[x][y] != 'o' )
a[x][y] = fix[i];
cur = go;
}
}
}
a[en.fi][en.se] = 'x';
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= m ; j++ )
cout << a[i][j];
cout << '\n';
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
#define TASK "__Whisper"
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
ll Test = 1; //cin >> Test;
for ( int i = 1 ; i <= Test ; i++ ){
Whisper();
//
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4516 KB |
Output is correct |
| 6 |
Correct |
30 ms |
38388 KB |
Output is correct |
| 7 |
Correct |
27 ms |
53552 KB |
Output is correct |
| 8 |
Correct |
68 ms |
60500 KB |
Output is correct |
| 9 |
Correct |
96 ms |
88924 KB |
Output is correct |
| 10 |
Correct |
175 ms |
96180 KB |
Output is correct |
| 11 |
Correct |
137 ms |
109536 KB |
Output is correct |
