【題解】AtCoder ABC 183E – Queen on Grid

#include <bits/stdc++.h>
using namespace std;

long long n, m, dp[2005][2005], p = 1e9+7, row[2005], col[2005], dia[4005];
string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> s;
        for (int j = 1; j <= m; j++){
            if (s[j-1] == '#'){
                row[i] = 0;
                col[j] = 0;
                dia[i-j+2000] = 0;
            }
            else{
                if (i == 1 && j == 1) dp[i][j] = 1;
                else{
                    dp[i][j] = row[i]+col[j]+dia[i-j+2000];
                    dp[i][j] %= p;
                }
                row[i] += dp[i][j];
                row[i] %= p;
                col[j] += dp[i][j];
                col[j] %= p;
                dia[i-j+2000] += dp[i][j];
                dia[i-j+2000] %= p;
            }
        }
    }
    cout << dp[n][m] << "\n";
}