Submission #39151958

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int H, W;
  cin >> H >> W;

  vector<string> G(H);
  for (int h = 0; h < H; ++h) cin >> G[h];

  using ARR = array<mint, 3>;
  vector<vector<ARR>> dp(H, vector<ARR>(W));
  dp[0][0][0] = 1;

  int dx[] = {0, 1};
  int dy[] = {1, 0};

  for (int x = 0; x < H; ++x) {
    for (int y = 0; y < W; ++y) {
      for (int d = 0; d < 2; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx == H || ny == W) continue;
        ARR& A = dp[x][y];
        ARR& B = dp[nx][ny];
        bool YY = (G[x][y] == 'Y' && G[nx][ny] == 'Y');
        if (!YY) {
          B[0] += A[0];
          B[1] += A[1];
          B[2] += A[2];
        }
        if (YY) {
          B[0] += A[0];
          B[1] += A[0] + A[1];
          B[2] += A[0] + A[1] + A[1] + A[2];
        }
      }
    }
  }
  mint ans = dp[H - 1][W - 1][2];
  cout << ans.val() << '\n';

  return 0;
}

Submission Info

Judge Result