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;
int dp[101][101][5001];
int solve(int r,int c,int 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]!='.')return 0;
if(pt==path.size()) {
if(dp[r][c][pt]!=-1) {
return 0;
}
dp[r][c][pt]=1;
return 1;
}
if(dp[r][c][pt]!=-1) {
return 0;
}
if(path[pt]=='?') {
dp[r][c][pt] = 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);
return dp[r][c][pt];
} else {
if(path[pt]=='W') {
dp[r][c][pt]= solve(r,c-1,pt+1,grid,path);
return dp[r][c][pt];
} else if(path[pt]=='E') {
dp[r][c][pt] = solve(r,c+1,pt+1,grid,path);
return dp[r][c][pt];
} else if(path[pt]=='N') {
dp[r][c][pt]= solve(r-1,c,pt+1,grid,path);
return dp[r][c][pt];
} else if(path[pt]=='S') {
dp[r][c][pt]= solve(r+1,c,pt+1,grid,path);
return dp[r][c][pt];
} else {
assert(0);
}
}
return 0;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int r;
cin >> r;
int c;
cin >> c;
int m;
cin >> m;
vector<string> grid;
for(int i = 0 ; i < r ; i++) {
string temp;
cin >> temp;
grid.push_back(temp);
}
string path;
cin >> path;
memset(dp,-1,sizeof dp);
int res=0;
for(int i = 0 ; i < r ; i++) {
for(int j = 0 ; j < c ; j++) {
res+=solve(i,j,0,grid,path);
}
}
cout << res << '\n';
return 0;
}
Compilation message (stderr)
nautilus.cpp: In function 'int solve(int, int, int, std::vector<std::__cxx11::basic_string<char> >&, std::string&)':
nautilus.cpp:9:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | if(r<0 or r>=grid.size() or c<0 or c>=grid[0].size())return 0;
| ~^~~~~~~~~~~~~
nautilus.cpp:9:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | if(r<0 or r>=grid.size() or c<0 or c>=grid[0].size())return 0;
| ~^~~~~~~~~~~~~~~~
nautilus.cpp:13:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | if(pt==path.size()) {
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |