目录

​编辑

题目描述

解题思路

具体代码

总结

问题描述:

解决方案:

代码实现:

关键点:


题目描述


棋盘上 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函数判断控制点,使用动态规划计算路径数量。

关键点:

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

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部