Edit

【pythonでABC183を解説】E - Queen on Grid

問題概要

問題ページ

E - Queen on Grid
E - Queen on Grid

問題ページへ移動する

問題文

縦 \(H\) マス、横 \(W\) マスのグリッドがあります。
上から \(i\) 行目、左から \(j\) 列目のマス \((i,j)\) は、\(S_{ij}\) が # のとき壁であり、. のとき道です。

マス \((1,1)\) にチェスのクイーンの駒が置いてあります。
クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに \(1\) 手で移動することができます。

クイーンの駒がマス \((1,1)\) からマス \((H,W)\) まで移動する方法は何通りありますか？ \(\bmod (10^9+7)\) で求めてください。

ただし、移動する方法が異なるとは、ある \(i\) が存在して、\(i\) 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。

制約

  • \(2 \leq H,W \leq 2000\)
  • \(S_{ij}\) は # か .
  • \(S_{11}\) と \(S_{HW}\) は .

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    dp = [[[0] * w for _ in range(h)] for _ in range(4)]
    dp[0][0][0] = 1
    for i in range(h):
        for j in range(w):
            dp[0][i][j] += (dp[1][i][j] + dp[2][i][j] + dp[3][i][j]) % mod
            if 0 <= i + 1 < h and s[i + 1][j] != "#":
                dp[1][i + 1][j] += (dp[0][i][j] + dp[1][i][j]) % mod
            if 0 <= j + 1 < w and s[i][j + 1] != "#":
                dp[2][i][j + 1] += (dp[0][i][j] + dp[2][i][j]) % mod
            if 0 <= i + 1 < h and 0 <= j + 1 < w and s[i + 1][j + 1] != "#":
                dp[3][i + 1][j + 1] += (dp[0][i][j] + dp[3][i][j]) % mod
    print(dp[0][-1][-1])


if __name__ == '__main__':
    solve()

-Edit
-