P1002 NOIP2002 普及组 过河卒 题解

本文最后更新于：2023年12月15日 晚上

题目描述

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0,0)(0, 0)、BB 点 (n,m)(n, m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例 #1

样例输入 #1

1
6 6 3 3

样例输出 #1

1
6

提示

对于 100%100 \% 的数据，1≤n,m≤201 \le n, m \le 20，0≤0 \le 马的坐标 ≤20\le 20。

【题目来源】

NOIP 2002 普及组第四题

解题思路

动态规划

本题是属于动态规划的题目，我们可以先从递归开始思考，同时用哈希表保存马的坐标

设马的坐标为(x,y)(x,y)，根据题目的xx和yy，得到以下坐标

  • (x+2,y−1)(x+2,y-1)
  • (x−2,y−1)(x-2,y-1)
  • (x+1,y−2)(x+1,y-2)
  • (x−1,y−2)(x-1,y-2)
  • (x+2,y+1)(x+2,y+1)
  • (x−2,y+1)(x-2,y+1)
  • (x+1,y+2)(x+1,y+2)
  • (x−1,y+2)(x-1,y+2)
  • (x,y)(x,y)

设dfs(i,j)dfs(i,j)，代表当前ii和jj的方案数，根据题目的可以向下、或者向右，向下即dfs(i+1,j)dfs(i+1,j)，向右即dfs(i,j+1)dfs(i,j+1)

最终得

dfs(i,j)=dfs(i+1,j)+dfs(i,j+1)dfs(i,j)=dfs(i+1,j)+dfs(i,j+1)

然后是递归边界了，当走到终点了，那就返回1，如果在搜索的时候遇到了马或者递归出边界，也要返回0，因为这是一个不合理的方案

这里是我用python演示

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
# 会超时的递归代码
a = input().split()
ma = (int(a[2]),int(a[3])) # 马的坐标
zd = (int(a[0]),int(a[1])) # 终点的坐标

ma_z = [] # 马的位置

p = [(2,-1),(-2,-1),(1,-2),(-1,-2),(2,1),(-2,1),(1,2),(-1,2),(0,0)]
for i in p:
    x = ma[0]+i[0]
    y = ma[1]+i[1]
    if x < 0  or y < 0:  # 如果计算的x和y是负数，代表不合理的坐标 跳过
        continue
    else:
        ma_z.append((x,y))# 添加进哈希表

def dfs(i,j):
    if i > zd[0] or j > zd[1]: # 如果递归出边界 代表不合理的方案 返回0
        return 0
    if (i,j) in ma_z: # 遇到了马 也要返回0
        return 0
    if i == zd[0] and j == zd[1]: # 到达了终点 返回1 代表这条路行得通
        return 1
    return dfs(i+1,j)+dfs(i,j+1) # 相加的方案数
print(dfs(0,0))

因为回溯搜索的复杂度是指数级别的，因此会超时，现在我们改成记忆化搜索

对了，这里python可以加个@catch，如果是其他语言可以开个数组保存搜索结果，我这里演示一下吧

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
26
27
28
29
30
a = input().split()
ma = (int(a[2]),int(a[3])) # 马的坐标
zd = (int(a[0]),int(a[1])) # 终点的坐标

ma_z = [] # 马的位置

p = [(2,-1),(-2,-1),(1,-2),(-1,-2),(2,1),(-2,1),(1,2),(-1,2),(0,0)]
for i in p:
    x = ma[0]+i[0]
    y = ma[1]+i[1]
    if x < 0  or y < 0:  # 如果计算的x和y是负数，代表不合理的坐标 跳过
        continue
    else:
        ma_z.append((x,y))# 添加进哈希表

catch = [[0 for _ in range(zd[1]+2)] for _ in range(zd[0]+2)] # 开个数组

def dfs(i,j):
    if i > zd[0] or j > zd[1]:
        return 0
    if catch[i][j] != 0: # 返回答案 记得写在判断边界下面
        return catch[i][j]
    if (i,j) in ma_z:
        return 0
    if zd[0] == i and j == zd[1]:
        return 1
    ans =  dfs(i+1,j)+dfs(i,j+1) # 用个变量存储
    catch[i][j] = ans # 保存答案
    return ans # 返回当前递归的答案
print(dfs(0,0))

好，这样就能通过本题目了

动态规划(迭代)

我们可以把递归改成迭代，但改成迭代之前要把递归中的递去掉，保留归，我们只需把干脆写的代码，返过来dp

之前是从起点到终点，我们现在改成从终点到起点，即

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
26
27
28
29
30
a = input().split()
ma = (int(a[2]),int(a[3])) # 马的坐标
zd = (int(a[0]),int(a[1])) # 终点的坐标

ma_z = [] # 马的位置

p = [(2,-1),(-2,-1),(1,-2),(-1,-2),(2,1),(-2,1),(1,2),(-1,2),(0,0)]
for i in p:
    x = ma[0]+i[0]
    y = ma[1]+i[1]
    if x < 0  or y < 0:  # 如果计算的x和y是负数，代表不合理的坐标 跳过
        continue
    else:
        ma_z.append((x,y))# 添加进哈希表

catch = [[0 for _ in range(zd[1]+2)] for _ in range(zd[0]+2)]

def dfs(i,j):
    if i < 0 or j < 0: # 如果超出了边界
        return 0
    if catch[i][j] != 0:
        return catch[i][j]
    if (i,j) in ma_z:
        return 0
    if i == 0 and j == 0: # 如果回到起点，说明这条路合理，方案数+1
        return 1
    ans =  dfs(i-1,j)+dfs(i,j-1)
    catch[i][j] = ans # 保存答案
    return ans
print(dfs(zd[0],zd[1]))

现在我们1:1翻译

dfs(i,j)=dfs(i−1,j)+dfs(i,j−1)dfs(i,j)=dfs(i-1,j)+dfs(i,j-1)

改成

dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j]+dp[i][j-1]

同时把起点初始化成1，即dp[0][0]=1dp[0][0]=1

因为直接从0开始的话，会出现负数下标，我们可以给-1的+1

dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]dp[i+1][j+1]=1dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]\\ dp[i+1][j+1] = 1 

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
a = input().split()
ma = (int(a[2]),int(a[3])) # 马的坐标
zd = (int(a[0]),int(a[1])) # 终点的坐标

ma_z = [] # 马的位置

p = [(2,-1),(-2,-1),(1,-2),(-1,-2),(2,1),(-2,1),(1,2),(-1,2),(0,0)]
for i in p:
    x = ma[0]+i[0]
    y = ma[1]+i[1]
    if x < 0  or y < 0:  # 如果计算的x和y是负数，代表不合理的坐标 跳过
        continue
    else:
        ma_z.append((x,y))# 添加进哈希表

dp = [[0 for _ in range(zd[1]+2)] for _ in range(zd[0]+2)]

#def dfs(i,j):
#    if i < 0 or j < 0:
#        return 0
#    if catch[i][j] != 0:
#        return catch[i][j]
#    if (i,j) in ma_z:
#        return 0
#    if i == 0 and j == 0:
#        return 1
#    ans =  dfs(i-1,j)+dfs(i,j-1)
#    catch[i][j] = ans # 保存答案
#    return ans

# 注意这里下面的操作都要+1
for i in range(0,zd[0]+1):
    for j in range(0,zd[1]+1):
        if i == j == 0:
            dp[i+1][j+1] = 1
        elif (i,j) in ma_z:
            dp[i+1][j+1] = 0
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
print(dp[zd[0]+1][zd[1]+1])

这样就是我们见到的动态规划了

代码示例

Python3

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
26
a = input().split()
ma = (int(a[2]),int(a[3])) # 马的坐标
zd = (int(a[0]),int(a[1])) # 终点的坐标

ma_z = [] # 马的位置

p = [(2,-1),(-2,-1),(1,-2),(-1,-2),(2,1),(-2,1),(1,2),(-1,2),(0,0)]
for i in p:
    x = ma[0]+i[0]
    y = ma[1]+i[1]
    if x < 0  or y < 0:  # 如果计算的x和y是负数，代表不合理的坐标 跳过
        continue
    else:
        ma_z.append((x,y))# 添加进哈希表

dp = [[0 for _ in range(zd[1]+2)] for _ in range(zd[0]+2)]

for i in range(0,zd[0]+1):
    for j in range(0,zd[1]+1):
        if i == j == 0:
            dp[i+1][j+1] = 1
        elif (i,j) in ma_z:
            dp[i+1][j+1] = 0
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
print(dp[zd[0]+1][zd[1]+1])

c++

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
26
27
28
29
30
31
32
// 注：c++题解来自官方题解
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//马可以走到的位置

int bx, by, mx, my;
ll f[40][40];
bool s[40][40]; //判断这个点有没有马拦住
int main(){
    scanf("%d%d%d%d", &bx, &by, &mx, &my);
    bx += 2; by += 2; mx += 2; my += 2;
    //坐标+2以防越界
    f[2][1] = 1;//初始化
    s[mx][my] = 1;//标记马的位置
    for(int i = 1; i <= 8; i++) s[mx + fx[i]][my + fy[i]] = 1;
    for(int i = 2; i <= bx; i++){
        for(int j = 2; j <= by; j++){
            if(s[i][j]) continue; // 如果被马拦住就直接跳过
            f[i][j] = f[i - 1][j] + f[i][j - 1];
            //状态转移方程
        }
    }
    printf("%lld\n", f[bx][by]);
    return 0;
}
code > 洛谷
#动态规划 #洛谷
P1002 NOIP2002 普及组 过河卒 题解
http://blog.bingyue.top/2023/12/15/p1002_luogu/
作者
bingyue
发布于
2023年12月15日
许可协议