제출 #310069

#제출 시각아이디문제언어결과실행 시간메모리
310069PetyNautilus (BOI19_nautilus)C++14
100 / 100
179 ms888 KiB
#include<bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

typedef long long ll;

int n, m, k;
bitset<502>v[502];
bitset<502>dp[2][502];


int main()
{
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      char ch;
      cin >> ch;
      if (ch == '.') {
        dp[1][i][j] = 1;
        v[i][j] = 1;
      }
    }
  string s;
  cin >> s;
  for (int ii = 0; ii < k; ii++) {
    for (int j = 1; j <= n;j++) {
      dp[ii % 2][j] = dp[1 - ii % 2][j];
    }
    for (int j = 1; j <= n; j++) {
      if (s[ii] == 'E')
        dp[ii % 2][j] = (dp[1 - ii % 2][j] << 1);
      if (s[ii] == 'W')
        dp[ii % 2][j] = (dp[1 - ii % 2][j] >> 1);
      if (s[ii] == 'N')
        dp[ii % 2][j] = (dp[1 - ii % 2][j + 1]);
      if (s[ii] == 'S')
        dp[ii % 2][j] = (dp[1 - ii % 2][j - 1]);
      if (s[ii] == '?') {
        dp[ii % 2][j] = (dp[1 - ii % 2][j] << 1);
        dp[ii % 2][j] |= (dp[1 - ii % 2][j] >> 1);
        dp[ii % 2][j] |= (dp[1 - ii % 2][j + 1]);
        dp[ii % 2][j] |= (dp[1 - ii % 2][j - 1]);
      }
      dp[ii % 2][j] &= (v[j]);
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      ans += dp[(k - 1) % 2][i][j];
  cout << ans;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...