趣味算法------过河卒

目录

​编辑

题目描述

解题思路

具体代码

总结

问题描述：

解决方案：

代码实现：

关键点：

题目描述

棋盘上 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)到棋盘上每个点的路径数量。

1. 函数check_place用于检查给定的点(r, l)是否在马的控制范围内。马的移动方向由数组dir定义，包含了马的八个可能的移动方向。

2. 初始化时，如果起点(0,0)不在马的控制范围内，则将arr[0][0]设置为1。

3. 接着，对于起点行和列的其他点，如果不在马的控制范围内，也将相应的arr元素设置为1，这是因为卒可以直接从起点到达这些点。

4. 对于棋盘上的其他点，卒可以通过向下或向右移动到达。如果当前点(i, j)不在马的控制范围内，则其路径数量为上一行对应点和左一列对应点路径数量之和，即arr[i][j] = arr[i - 1][j] + arr[i][j - 1]。

5. 最后，输出数组中目标点(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;
		else
			break;
	}
	for (int i = 1; i <= M; i++)
	{
		if (!check_place(i, 0, m,n))
			arr[i][0] = 1;
		else
			break;
	}
	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点的路径数量，且这些路径不能经过马的控制点。

解决方案：

1. 定义控制点： 马的控制点包括马所在位置及其八个方向上可以到达的点。通过一个辅助函数check_place判断任意点是否为控制点。
2. 动态规划：
   • 初始化一个二维数组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]更新其他点的路径数量，前提是该点不在马的控制点范围内。
3. 输出结果： 最终，arr[n][m]即为从A点到B点的路径数量。

代码实现：

使用C语言实现上述逻辑，通过check_place函数判断控制点，使用动态规划计算路径数量。

关键点：

• 动态规划的递推关系和边界条件设置。
• 识别并排除马的控制点。