| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 857151 | Trisanu_Das | Nautilus (BOI19_nautilus) | C++17 | 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;
int r, c, m, ans;
char a[500][500];
string s;
int dp[500][500][5000];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void paths(int x, int y, int far){
if(x < 0 || x >= r || y < 0 || y >= c || a[x][y] == '#') return;
if(far == m){
ans++; return;
}
if(dp[x][y][far]) return;
dp[x][y][far] = 1;
if(s[far] == 'N') paths(x - 1, y, far + 1);
else if(s[far] == 'S') paths(x + 1, y, far + 1);
else if(s[far] == 'W') paths(x, y - 1, far + 1);
else if(s[far] == 'E') paths(x, y + 1, far + 1);
else for(int d = 0; d < 4; d++) paths(x + dx[d], y + dy[d], far + 1);
}
int main(){
cin >> r >> c >> m;
for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) cin >> a[i][j];
cin >> s;
for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(a[i][j] != '#') paths(i, j, 0);
cout << ans << '\n';
}