| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 328788 |
2020-11-18T05:13:35 Z |
egas |
Nautilus (BOI19_nautilus) |
C++14 |
|
137 ms |
262148 KB |
#include <bits/stdc++.h>
using namespace std;
long long dp[101][101][5001];
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]!='.')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);
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;
memset(dp,-1,sizeof dp);
long long res=0;
for(long long i = 0 ; i < r ; i++) {
for(long long j = 0 ; j < c ; j++) {
res+=solve(i,j,0,grid,path);
}
}
cout << res << '\n';
return 0;
}
Compilation message
nautilus.cpp: In function 'long long int solve(long long int, long long int, long long int, std::vector<std::__cxx11::basic_string<char> >&, std::string&)':
nautilus.cpp:9:16: warning: comparison of integer expressions of different signedness: 'long long 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: 'long long 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: 'long long 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 |
| 1 |
Runtime error |
137 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
