Submission #1021862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021862		basa	Nautilus (BOI19_nautilus)	C++14	66 / 100	383 ms	262144 KiB

nautilus

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
string m;
int r, c, k;
string s[605];
bool vis[605][605][5005];
 
int dfs(int i, int j, int p){
  if(i >= r || i < 0) return 0;
  if(j >= c || j < 0) return 0;
  if(s[i][j] == '#') return 0;
  if(vis[i][j][p]) return 0;
  vis[i][j][p] = 1;
  if(p == (int)m.size()) return 1;
 
 
  int ret = 0;
 
  if(m[p] == 'N') ret = dfs(i - 1, j, p + 1);
  if(m[p] == 'S') ret = dfs(i + 1, j, p + 1);
  if(m[p] == 'E') ret = dfs(i, j + 1, p + 1);
  if(m[p] == 'W') ret = dfs(i, j - 1, p + 1);
 
  if(m[p] == '?'){
    ret += dfs(i + 1, j, p + 1);
    ret += dfs(i - 1, j, p + 1);
    ret += dfs(i, j + 1, p + 1);
    ret += dfs(i, j - 1, p + 1);
  }
 
  return ret;
}
 
signed main()
{
  cin.tie(0) -> sync_with_stdio(0);
  cin >> r >> c >> k;
 
  for(int i = 0; i < r; i++) cin >> s[i];
 
  cin >> m;
 
  int ans = 0;
  for(int i = 0; i < r; i++){
    for(int j = 0; j < c; j++){
      if(s[i][j] == '#') continue;
      ans += dfs(i, j, 0);
    }
  }
 
  cout << ans;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34