題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1002 [NOIP 2002 普及组] 过河卒

Problem Statement

題目簡述

在一個座標棋盤上，卒從左上角出發，每次只能向右或向下走一步，目標是走到指定終點。
棋盤上另有一匹馬，馬所在的位置以及牠一步可攻擊到的位置都不能經過。
請計算卒在避開所有禁止格子的情況下，有多少種不同走法可以到達終點。

Constraints

約束條件

  • 終點座標與馬的位置座標皆在 0≤x,y≤200 \le x, y \le 20 範圍內

思路：記憶化搜尋

卒只能往右或往下走，所以抵達某個合法位置的路徑數，只會來自上方與左方兩個方向：

ways(x,y)=ways(x−1,y)+ways(x,y−1) \text{ways}(x, y)=\text{ways}(x-1, y)+\text{ways}(x, y-1)

先把馬所在位置與馬能攻擊到的八個位置都標成禁止格。搜尋時若遇到越界或禁止格，表示這條路不合法，回傳 00；若回到起點，代表找到一條合法路徑，回傳 11。

為了避免重複計算同一個位置的路徑數，可以用記憶化搜尋（Memoization）把已經計算過的位置與對應的路徑數記錄下來，當再次遇到同一位置時直接回傳結果。

最終答案就是 ways(xend,yend)\text{ways}(x_{end}, y_{end})，其中 (xend,yend)(x_{end}, y_{end}) 是終點座標。

複雜度分析

  • 時間複雜度：O(NM)\mathcal{O}(NM)，其中 NN、MM 為終點座標範圍內的棋盤長寬，每個位置最多計算一次。
  • 空間複雜度：O(NM)\mathcal{O}(NM)，用於記憶化快取與遞迴呼叫堆疊。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from functools import cache


def solve():
    x1, y1, x2, y2 = map(int, input().split())

    bans = set([(x2, y2)])
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) + abs(dy) == 3:
                bans.add((x2 + dx, y2 + dy))

    @cache
    def dfs(i: int, j: int) -> int:
        if i < 0 or j < 0 or (i, j) in bans:
            return 0
        if i == 0 and j == 0:
            return 1
        return dfs(i - 1, j) + dfs(i, j - 1)

    print(dfs(x1, y1))


if __name__ == "__main__":
    solve()