/* -*- coding: utf-8 -*- * * 3071.cc: No.3071 Double Speedrun - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_H = 400; const int MAX_W = 400; const int MAX_WW = MAX_W * MAX_W; const int MOD = 998244353; /* typedef */ /* global variables */ char fs[MAX_H][MAX_W + 4]; int dp[2][MAX_WW]; /* subroutines */ inline void addmod(int &a, int b) { a = (a + b) % MOD; } /* main */ int main() { int h, w; scanf("%d%d", &h, &w); for (int i = 0; i < h; i++) scanf("%s", fs[i]); int maxi = h + w - 3, ww = w * w; int cur = 0, nxt = 1; dp[0][0 * w + 1] = 1; for (int i = 1; i < maxi; i++) { fill(dp[nxt], dp[nxt] + ww, 0); int x0 = min(i, w - 1) - 1, y0 = i - x0; for (; x0 >= 0 && y0 < h; x0--, y0++) if (fs[y0][x0] == '.') { int x1 = min(i, w - 1), y1 = i - x1; for (; x1 > x0; x1--, y1++) if (fs[y1][x1] == '.') { int u = x0 * w + x1; if (dp[cur][u]) { //printf(" i=%d,x0=%d,x1=%d: %d\n", i, x0, x1, dp[cur][u]); for (int di0 = 0; di0 < 2; di0++) { int vy0 = y0 + (1 - di0), vx0 = x0 + di0; if (vy0 < h && vx0 < w && fs[vy0][vx0] == '.') for (int di1 = 0; di1 < 2; di1++) { int vy1 = y1 + (1 - di1), vx1 = x1 + di1; if (vy1 < h && vx0 < w && fs[vy1][vx1] == '.' && vx0 != vx1) { int v = vx0 * w + vx1; addmod(dp[nxt][v], dp[cur][u]); } } } } } } swap(cur, nxt); } printf("%d\n", dp[cur][(w - 2) * w + (w - 1)]); return 0; }