#include<bits/stdc++.h>
using namespace std;
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};
#define f first
#define s second
struct st
{
int i,j,w;
};
int main()
{
int n,m;
cin>>n>>m;
string s[n];
int oi,oj;
for(int i=0;i<n;i++)
{
cin>>s[i];
for(int j=0;j<m;j++)
{
if(s[i][j]=='o')
{
oi=i,oj=j;
}
}
}
queue<st> q;
char c='O';
int ans=INT_MAX;
if(oj+1<m&&(s[oi][oj+1]=='x'))
{
cout<<":)\nE";
return 0;
}
if(oi-1>=0&&(s[oi-1][oj]=='x'))
{
cout<<":)\nN";
return 0;
}
if(oi+1<n&&(s[oi+1][oj]=='x'))
{
cout<<":)\nS";
return 0;
}
if(oj-1>=0&&(s[oi][oj-1]=='x'))
{
cout<<":)\nW";
return 0;
}
//int dist[n][m];
//memset(dist,127,sizeof dist);
if(oj+1<m&&(s[oi][oj+1]!='.'))
{
q.push({oi,oj+1,1});
//dist[oi][oj+1]=1;
while(!q.empty())
{
auto p=q.front();
q.pop();
int i=p.i,j=p.j,w=p.w;
if(s[i][j]=='x')
{
ans=w;
c='E';
break;
}
if(s[i][j]=='.'||s[i][j]=='o')
continue;
if(s[i][j]=='>')
q.push({i,j+1,w+1});
else if(s[i][j]=='<')
q.push({i,j-1,w+1});
else if(s[i][j]=='^')
q.push({i-1,j,w+1});
else
q.push({i+1,j,w+1});
}
}
if(oi-1>=0&&(s[oi-1][oj]!='.'))
{
while(!q.empty())
q.pop();
q.push({oi-1,oj,1});
//dist[oi][oj+1]=1;
while(!q.empty())
{
auto p=q.front();
q.pop();
int i=p.i,j=p.j,w=p.w;
if(s[i][j]=='x')
{
if(ans>w)
{
ans=w;
c='N';
}
break;
}
if(s[i][j]=='.'||s[i][j]=='o')
continue;
if(s[i][j]=='>')
q.push({i,j+1,w+1});
else if(s[i][j]=='<')
q.push({i,j-1,w+1});
else if(s[i][j]=='^')
q.push({i-1,j,w+1});
else
q.push({i+1,j,w+1});
}
}
if(oi+1<n&&(s[oi+1][oj]!='.'))
{
while(!q.empty())
q.pop();
q.push({oi+1,oj,1});
//dist[oi][oj+1]=1;
while(!q.empty())
{
auto p=q.front();
q.pop();
int i=p.i,j=p.j,w=p.w;
if(s[i][j]=='x')
{
if(ans>w)
{
ans=w;
c='S';
}
break;
}
if(s[i][j]=='.'||s[i][j]=='o')
continue;
if(s[i][j]=='>')
q.push({i,j+1,w+1});
else if(s[i][j]=='<')
q.push({i,j-1,w+1});
else if(s[i][j]=='^')
q.push({i-1,j,w+1});
else
q.push({i+1,j,w+1});
}
}
if(oj-1>=0&&(s[oi][oj-1]!='.'))
{
while(!q.empty())
q.pop();
q.push({oi,oj-1,1});
//dist[oi][oj+1]=1;
while(!q.empty())
{
auto p=q.front();
q.pop();
int i=p.i,j=p.j,w=p.w;
if(s[i][j]=='x')
{
if(ans>w)
{
ans=w;
c='W';
}
break;
}
if(s[i][j]=='.'||s[i][j]=='o')
continue;
if(s[i][j]=='>')
q.push({i,j+1,w+1});
else if(s[i][j]=='<')
q.push({i,j-1,w+1});
else if(s[i][j]=='^')
q.push({i-1,j,w+1});
else
q.push({i+1,j,w+1});
}
}
if(c!='O')
{
cout<<":)\n";
cout<<c;
}
else
cout<<":(";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |