atcoder abc183 E - Queen on Grid

問題

解法

DP + 累積和。

dp配列は、 dp[i][j] = {i,j}地点に到達できる場合の数 で考える。

するとdp[i][j] は以下のように3方向のdpの累積を足すと求められる。

dp[i][j] = dp[i][j-1] + dp[i][j-2] ... + dp[i][0]
 + dp[i-1][j] + dp[i-2][j] ... + dp[0][j]
 + dp[i-1][j-1] + dp[i-2][j-2] ... + dp[0][0]

毎回dpの累積を計算すると計算量が増えてしまうため、累積和で高速化する。

dp[i][j] = 右移動の累積和 + 下移動の累積和 + 右下移動の累積

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
// mint は省略

const int MX = 2005;
int h,w;
char s[MX][MX];
mint dp[MX][MX];
mint x[MX][MX], y[MX][MX], z[MX][MX]; // 3方向それぞれの累積和. x: 右方向, y: 下方向, z: 右下方向

void f(int i, int j) {
  if (s[i][j] == '#') return;

  if (0 <= j-1) x[i][j] = x[i][j-1] + dp[i][j-1];
  if (0 <= i-1) y[i][j] = y[i-1][j] + dp[i-1][j];
  if (0 <= i-1 && 0 <= j-1) z[i][j] = z[i-1][j-1] + dp[i-1][j-1];

  dp[i][j] = x[i][j] + y[i][j] + z[i][j];
}

int main() {
  cin >> h >> w;
  REP(i,h) REP(j,w) cin >> s[i][j];

  dp[0][0] = 1;
  REP(i,h) REP(j,w) {
    if (i == 0 && j == 0) continue;
    f(i,j);
  }

  cout << dp[h-1][w-1] << endl;
  return 0;
}