This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
string s[105];
int dp[105][105];
int sx, sy, gx, gy;
char ans='.';
int mn=1e12;
int tmp=-1;
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
string dir="NSWE";
void bfs(int x, int y){
queue<pair<int,int>> q;
q.push({x,y});
dp[x][y]=2;
while(!q.empty()){
int curx=q.front().first, cury=q.front().second;
q.pop();
// if(curx==gx and cury==gy){
//
// }
if(s[curx][cury]=='v'){
if(!dp[curx+1][cury]){
q.push({curx+1,cury});
dp[curx+1][cury]=dp[curx][cury]+1;
}
}
else if(s[curx][cury]=='^'){
if(!dp[curx-1][cury]){
q.push({curx-1,cury});
dp[curx-1][cury]=dp[curx][cury]+1;
}
}
else if(s[curx][cury]=='<'){
if(!dp[curx][cury-1]){
q.push({curx,cury-1});
dp[curx][cury-1]=dp[curx][cury]+1;
}
}
else if(s[curx][cury]=='>'){
if(!dp[curx][cury+1]){
q.push({curx,cury+1});
dp[curx][cury+1]=dp[curx][cury]+1;
}
}
}
if(!dp[gx][gy]) tmp=-1;
else tmp=dp[gx][gy];
}
signed main(){
cin>>n>>m;
for(int i=0; i<n; i++){
cin>>s[i];
for(int j=0; j<s[i].size(); j++){
if(s[i][j]=='o'){
sx=i, sy=j;
}
if(s[i][j]=='x'){
gx=i, gy=j;
}
}
}
for(int i=0; i<4; i++){
int nx=dx[i]+sx, ny=dy[i]+sy;
memset(dp,sizeof(dp),0);
for(int j=0; j<n; j++){
for(int k=0; k<m; k++){
dp[j][k]=0;
}
}
dp[sx][sy]=1;
if(nx>=0 and nx<n and ny>=0 and ny<m){
dp[nx][ny]=2;
tmp=-1;
bfs(nx,ny);
if(tmp==-1) continue;
else{
if(tmp<mn){
mn=tmp;
ans=dir[i];
}
else if(tmp==mn){
if(ans>dir[i]) ans=dir[i];
}
}
}
}
if(ans=='.'){
cout<<":("<<endl;
}
else{
cout<<":)"<<endl;
cout<<ans<<endl;
}
}
Compilation message (stderr)
patkice.cpp: In function 'int main()':
patkice.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int j=0; j<s[i].size(); j++){
| ~^~~~~~~~~~~~
patkice.cpp:67:25: warning: 'memset' used with constant zero length parameter; this could be due to transposed parameters [-Wmemset-transposed-args]
67 | memset(dp,sizeof(dp),0);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |