目录
编辑
题目描述
解题思路
具体代码
总结
问题描述:
解决方案:
代码实现:
关键点:
题目描述
棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A 点(0,0) 、B 点(n,m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 B 点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
输入输出样例
输入 1
6 6 3 3
输出 1
6
输入 6 6 表示 B 点的坐标,3 3 表示马的坐标,输出 6 表示除去马的坐标以及所有跳跃一步可达的点,从 A 点出发到 B 点的所有的路径条数。
解题思路
在解决这个问题之前我要先引入一个例子,假设小明站在二维坐标图的原点位置,并且一次只能走上右一格距离,并且已经走过的地方不能再走,而且只能走最短距离,那么他到(1,0),(0,1)方案肯定是1,那么(1,1)方案数就为2,由(1,1)再往外扩展的一个方案数就为3,是典型的动态规划问题。
代码的思路是使用动态规划来解决“马拦过河卒”问题。动态规划数组arr
的大小为maxlen x maxlen
,用于存储从起点(0,0)到棋盘上每个点的路径数量。
-
函数
check_place
用于检查给定的点(r, l)是否在马的控制范围内。马的移动方向由数组dir
定义,包含了马的八个可能的移动方向。 -
初始化时,如果起点(0,0)不在马的控制范围内,则将
arr[0][0]
设置为1。 -
接着,对于起点行和列的其他点,如果不在马的控制范围内,也将相应的
arr
元素设置为1,这是因为卒可以直接从起点到达这些点。 -
对于棋盘上的其他点,卒可以通过向下或向右移动到达。如果当前点(i, j)不在马的控制范围内,则其路径数量为上一行对应点和左一列对应点路径数量之和,即
arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
。 -
最后,输出数组中目标点(M, N)的值,即为卒从起点到目标点的路径数量。
这种方法的时间复杂度为O(MN),空间复杂度为O(MN),其中M和N分别是棋盘的行数和列数。通过这种方式,代码能够计算出在马的控制下,卒从起点到目标点的所有可能路径的数量。
具体代码
#include<stdio.h>
#include<stdlib.h>
#define maxlen 100
int check_place(int r, int l, int h_r, int h_l)
{int dir[8][2] = { {2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2} };for (int i = 0; i < 8; i++)if ((dir[i][1] + h_l == l && dir[i][0] + h_r == r)||(r == h_r &&h_l == l))return 1;return 0;
}
int main(void)
{int arr[maxlen][maxlen] = { {1} };int M, N, m, n;scanf("%d%d%d%d", &M, &N, &m, &n);for (int i = 1; i <= N; i++){if (!check_place(0, i, m,n))arr[0][i] = 1;elsebreak;}for (int i = 1; i <= M; i++){if (!check_place(i, 0, m,n))arr[i][0] = 1;elsebreak;}for(int i = 1;i<=M;i++)for (int j = 1; j <= N; j++){if (!check_place(i, j, m, n))arr[i][j] = arr[i - 1][j] + arr[i][j - 1];}printf("%d", arr[M][N]);return 0;}
总结
问题描述:
在棋盘上,有一个过河卒从点A(0,0)出发,目标是到达点B(n,m)。过河卒可以向下或向右移动。棋盘上存在一个对方的马,位于点C。马及其控制的八个方向上的点被定义为“马的控制点”。任务是计算出卒从A点到达B点的路径数量,且这些路径不能经过马的控制点。
解决方案:
- 定义控制点: 马的控制点包括马所在位置及其八个方向上可以到达的点。通过一个辅助函数
check_place
判断任意点是否为控制点。 - 动态规划:
- 初始化一个二维数组
arr
,其中arr[i][j]
表示从A点到达(i,j)的路径数量。 - 初始条件:
arr[0][0] = 1
,表示起点到自身的路径数量为1。 - 对于第一行和第一列,如果不在马的控制点范围内,则
arr[i][0]
和arr[0][j]
的值为1,表示可以直接到达。 - 通过动态规划递推公式
arr[i][j] = arr[i-1][j] + arr[i][j-1]
更新其他点的路径数量,前提是该点不在马的控制点范围内。
- 初始化一个二维数组
- 输出结果: 最终,
arr[n][m]
即为从A点到B点的路径数量。
代码实现:
使用C语言实现上述逻辑,通过check_place
函数判断控制点,使用动态规划计算路径数量。
关键点:
- 动态规划的递推关系和边界条件设置。
- 识别并排除马的控制点。