# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
328783 | egas | Nautilus (BOI19_nautilus) | C++14 | 0 ms | 0 KiB |
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;
set<pair<long long,long long> > ss;
long long solve(long long r,long long c,long long pt,vector<string> &grid,string &path) {
if(r<0 or r>=grid.size() or c<0 or c>=grid[0].size())return 0;
if(grid[r][c]=='
if(pt==path.size()){
ss.insert({r,c});
return 1;
}
if(path[pt]=='?') {
return solve(r,c-1,pt+1,grid,path) + solve(r,c+1,pt+1,grid,path) + solve(r-1,c,pt+1,grid,path) + solve(r+1,c,pt+1,grid,path);
} else {
if(path[pt]=='W') {
return solve(r,c-1,pt+1,grid,path);
} else if(path[pt]=='E') {
return solve(r,c+1,pt+1,grid,path);
} else if(path[pt]=='N') {
return solve(r-1,c,pt+1,grid,path);
} else if(path[pt]=='S') {
return solve(r+1,c,pt+1,grid,path);
} else {
assert(0);
}
}
return 0;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
long long r;
cin >> r;
long long c;
cin >> c;
long long m;
cin >> m;
vector<string> grid;
for(long long i = 0 ; i < r ; i++) {
string temp;
cin >> temp;
grid.push_back(temp);
}
string path;
cin >> path;
for(long long i = 0 ; i < r ; i++) {
for(long long j = 0 ; j < c ; j++) {
solve(i,j,0,grid,path);
}
}
cout << ss.size() << '\n';
return 0;
}