[AtCoder] ABC 183 E – Queen on Grid

2020年11月16日2020年12月12日

問題

方針

まず、壁がない場合を考えます。

\( 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;
}