#include<bits/stdc++.h>
using namespace std;
const int mx=20;
typedef long long ll;
int inf=1e6;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
char c[4]={'v','^','>','<'};
int n,m;
bool valid(int x,int y){
if(x>=n||y>=m||x<0||y<0){return 0;}
return 1;
}
int main(){
cin>>n>>m;
int sx;int sy ;
int enx;int eny;
int b[n][m];
string s[n];
memset(b,-1,sizeof(b));
for(int i=0;i<n;i++){
cin>>s[i];
for(int j=0;j<m;j++){
for(int l=0;l<4;l++){
if(s[i][j]==c[l]){
b[i][j]=l;
}
}
if(s[i][j]=='o'){
sx=i;
sy=j;
}
if(s[i][j]=='x'){
enx=i;
eny=j;
}
}
}
deque<pair<int,int>>dq;
int dis[n+2][m+2];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dis[i][j]=inf;
}
}
dis[sx][sy]=0;
int trace[n+1][m+1];
dq.push_back({sx,sy});
while(!dq.empty()){
pair<int,int>me=dq.front();
int x=me.first;
int y=me.second;
dq.pop_front();
for(int i=0;i<4;i++){
int nx=me.first+dx[i];
int ny=me.second+dy[i];
int cost=dis[x][y];
if(b[x][y]==i){
}else{
cost++;
}
if(valid(nx,ny)){
if(cost<dis[nx][ny]){
dis[nx][ny]=cost;
trace[nx][ny]=i;
if(b[x][y]!=i){
dq.push_back({nx,ny});
}else{
dq.push_front({nx,ny});
}
}
}
}
}
cout<<dis[enx][eny]-1<<endl;
int l=dis[enx][eny];
while(enx!=sx&&eny!=sy){
int dir=trace[enx][eny];
enx-=dx[dir];eny-=dy[dir];
if(l>0){
s[enx][eny]=c[dir];}
if(b[enx][eny]!=dir){
l--;
}
}
for(int i=0;i<n;i++){
cout<<s[i]<<endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:98:14: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
98 | while(enx!=sx&&eny!=sy){
| ~~~~~~~^~~~~~~~~
Main.cpp:98:14: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
Main.cpp:96:19: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
96 | cout<<dis[enx][eny]-1<<endl;
| ~~~~~~~~~~~~^
Main.cpp:96:19: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Partially correct |
1 ms |
204 KB |
Partially correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Partially correct |
1 ms |
204 KB |
Partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Partially correct |
1 ms |
204 KB |
Partially correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Partially correct |
1 ms |
204 KB |
Partially correct |
| 6 |
Correct |
46 ms |
7192 KB |
Output is correct |
| 7 |
Partially correct |
48 ms |
8612 KB |
Partially correct |
| 8 |
Partially correct |
131 ms |
18708 KB |
Partially correct |
| 9 |
Correct |
194 ms |
32708 KB |
Output is correct |
| 10 |
Partially correct |
318 ms |
43392 KB |
Partially correct |
| 11 |
Correct |
331 ms |
53952 KB |
Output is correct |
