[AtCoder] ABC 183 E – Queen on Grid
問題
方針
まず、壁がない場合を考えます。
\( d(i, j) \) をマス \( (1, 1)\) から マス \( (i, j) \) への移動方法の数とします。\( d(i, j) \) は、\( n = \min (i, j) \) として、
\begin{eqnarray}
d(i, j) &=& d(i – 1, i) + d(i – 2, i) + \cdots + d(1, i)\\
&+& d(i, j – 1) + d(i, j – 2) + \cdots + d(j, 1) \\
&+& d(i – 1, i – 1) + d(i – 2, i – 2) + \cdots + d(i – n, j – n) \\
&=& \sum_{k = 1} ^{i – 1} d(i – k, j) + \sum_{k = 1} ^{j- 1} d(i , j – k) + \sum_{k = 1} ^{n – 1} d(i – k, j – k)
\end{eqnarray}
となります。また、\( d(1, 1) = 1\) です。ここで、\( a(i, j), b(i, j), c(i, j) \) を
\begin{eqnarray}
a(i, j) &=& \sum_{k = 1} ^{i – 1} d(i – k, j) \\
b(i, j) &=& \sum_{k = 1} ^{j – 1} d(i, j – k) \\
c(i, j) &=& \sum_{k = 1} ^{n – 1} d(i – k, j – k) \\
\end{eqnarray}
とすると、
\[ d(i, j) = a(i, j) + b(i, j) + c(i, j)\]
となります。また、\( a(i, j), b(i, j), c(i, j) \) は
\begin{eqnarray}
a(i, j) &=& a(i – 1, j) + d(i – 1, j)\\
b(i, j) &=& b(i, j – 1) + d(i, j – 1)\\
c(i, j) &=& c(i – 1, j – 1) + d(i – 1, j – 1)
\end{eqnarray}
となるので、累積和として高速に計算できます。壁を考慮するときは、マス \( (i -1 , j) \) 、マス \( (i, j – 1) \) 、マス \( (i – 1, j – 1)\) からマス \( (i, j)\) へと移動することができるかどうかを調べます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1000000007; const int MAX = 2001; ll a[MAX][MAX]{}; ll b[MAX][MAX]{}; ll c[MAX][MAX]{}; ll d[MAX][MAX]{}; int g[MAX][MAX]{}; int main() { int H, W; cin >> H >> W; string S[H]; for (int i = 0; i < H; i++) { cin >> S[i]; for (int j = 0; j < W; j++) { if (S[i][j] == '.') { g[i][j] = 1; } } } d[0][0] = 1; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (g[i][j] == 0) continue; if (i == 0 && j == 0) continue; if (i - 1 >= 0 && g[i - 1][j] == 1) { a[i][j] = (a[i - 1][j] + d[i - 1][j]) % mod; } if (j - 1 >= 0 && g[i][j - 1] == 1) { b[i][j] = (b[i][j - 1] + d[i][j - 1]) % mod; } if (i - 1 >= 0 && j - 1 >= 0 && g[i - 1][j - 1] == 1) { c[i][j] = (c[i - 1][j - 1] + d[i - 1][j - 1]) % mod; } d[i][j] = (a[i][j] + b[i][j] + c[i][j]) % mod; } } cout << d[H - 1][W - 1] << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません