#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> g;
vector <int> keys;
vector <set<int>> ans;
map <pair<int, int>, bool> mapa;
int pr(char s)
{
if (s=='X') return 0;
if (s=='N') return 1;
if (s=='E') return 2;
if (s=='S') return 3;
if (s=='W') return 4;
}
void fushdfs (int node, int parent, int n, int m)
{
if (mapa[{parent, node}]) return;
mapa[{parent, node}]=true;
if (keys[node]==pr('X'))
{
return;
}
int i=node/m, j=node%m;
int strel=keys[node], prvi=*ans[node].begin();
if (j<m-1)
{
ans[node+1].insert(prvi+(pr('E')-strel+4)%4);
fushdfs(node+1, node, n, m);
}
if (j>0)
{
ans[node-1].insert(prvi+(pr('W')-strel+4)%4);
fushdfs(node-1, node, n, m);
}
if (i<n-1)
{
ans[node+m].insert(prvi+(pr('S')-strel+4)%4);
fushdfs(node+m, node, n, m);
}
if (i>0)
{
ans[node-m].insert(prvi+(pr('N')-strel+4)%4);
fushdfs(node-m, node, n, m);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin>>n>>m;
g.resize(m*n);
keys.resize(m*n);
ans.resize(m*n);
ans[0].insert(0);
for (int i=0; i<n; i++)
{
string str; cin>>str;
for (int j=0; j<m; j++)
{
char s=str[j];
int node=i*m+j;
keys[node]=pr(s);
if (s=='E' && j!=m-1) g[node].push_back(node+1);
if (s=='W' && j!=0) g[node].push_back(node-1);
if (s=='S' && i!=n-1) g[node].push_back(node+m);
if (s=='N' && i!=0) g[node].push_back(node-m);
}
}
fushdfs(0, -1, n, m);
if (!ans[n*m-1].empty()) cout<<*ans[n*m-1].begin()<<endl;
else cout<<-1<<endl;
return 0;
}
Compilation message (stderr)
adventure.cpp: In function 'int pr(char)':
adventure.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
14 | }
| ^| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |