#include <bits/stdc++.h>
#define ff first
#define ss second
#define mkt make_tuple
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define tiiii tuple<int,int,int, int>
const int MAX = 2010 ;
const int inf = 1e9+10 ;
using namespace std ;
int N , M ;
int dx[4] = { 0, 1 , 0 , -1} , dy[4] = {1,0,-1,0} ;
int grid[MAX][MAX] , dist[MAX][MAX][4] ;
tuple<int,int,int> par[MAX][MAX][4 ] ;
pair<int,int> S , T ;
priority_queue< tiiii , vector<tiiii>, greater<tiiii> > fila ;
bool valid(int x, int y) { return 1 <= min(x,y) && x <= N && y <= M; }
int main()
{
scanf("%d %d", &N, &M ) ;
for(int i = 1 ; i <= N ; i++ )
for(int j = 1 ; j <= M ; j++ )
{
char c ;
scanf(" %c", &c ) ;
if(c == 'v') grid[i][j] = 1 ;
if( c == '<' ) grid[i][j] = 2 ;
if( c == '^' ) grid[i][j] = 3 ;
if( c == 'o' ) S = mk(i,j) , grid[i][j] = -1 ;
if( c == 'x' ) T = mk(i,j) , grid[i][j] = -2 ;
if(c == '.') grid[i][j] = 4 ;
}
for(int i = 1 ; i <= N ; i++ )
for(int j = 1 ; j <= M ; j++ )
for(int g = 0 ; g < 4 ; g++ ) dist[i][j][g] = inf ;
for(int g = 0 ; g < 4 ; g++ )
{
dist[S.first][S.second][g] = 0 ;
fila.push( mkt(0, S.ff, S.ss,g) ) ;
}
tuple<int,int,int> cur ;
while(!fila.empty())
{
int d = get<0>(fila.top()) ;
int x = get<1>(fila.top()) ;
int y = get<2>(fila.top());
int g = get<3>(fila.top()) ;
fila.pop() ;
if( d != dist[x][y][g] ) continue ;
if(x == T.ff && y == T.ss )
{
printf("%d\n" , dist[x][y][g]) ;
cur = par[x][y][g] ;
break ;
}
int nx = x + dx[g] ;
int ny = y + dy[g] ;
if(!valid(nx, ny)) continue ;
for(int i = 0 , nd ; i < 4 ; i++ )
{
nd = dist[x][y][g] ;
if( i != grid[nx][ny] && grid[nx][ny] >= 0 ) nd++ ;
if(nd >= dist[nx][ny][i]) continue ;
par[nx][ny][i] = mkt(x,y,g) ;
fila.push( mkt( dist[nx][ny][i] = nd , nx, ny, i ) ) ;
}
}
int x = get<0>(cur) , y = get<1>(cur) , g = get<2>(cur) ;
while(!(mk(x,y) == S))
{
grid[x][y] = g ;
cur = par[x][y][g] ;
x = get<0>(cur) , y = get<1>(cur), g = get<2>(cur) ;
}
lp(i,1,N+1)
{
lp(j,1,M+1)
{
if( grid[i][j] == 0 ) printf(">") ;
if( grid[i][j] == 1 ) printf("v") ;
if( grid[i][j] == 2 ) printf("<") ;
if( grid[i][j] == 3 ) printf("^") ;
if( grid[i][j] == -1 ) printf("o") ;
if( grid[i][j] == -2 ) printf("x") ;
if( grid[i][j] == 4 ) printf(".") ;
}
printf("\n") ;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d %d", &N, &M ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf(" %c", &c ) ;
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
428 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
428 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
258 ms |
30672 KB |
Output is correct |
| 7 |
Correct |
244 ms |
52132 KB |
Output is correct |
| 8 |
Correct |
886 ms |
82556 KB |
Output is correct |
| 9 |
Correct |
1593 ms |
170048 KB |
Output is correct |
| 10 |
Execution timed out |
2098 ms |
182244 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
