洛谷题解P1002_过河卒

题目描述

棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点 (0,0)、B点 (n,m)，同样马的位置坐标是需要给出的。

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

输入格式

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

输出格式

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

输入输出样例

输入 6 6 3 3
输出 6

说明/提示

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

【题目来源】

NOIP 2002 普及组第四题

题目分析

马走日这一点不要忽视。

（对于不下象棋的人很容易忽视，比如说，我）
接下来分析题目
可以看到 卒的行走规则为向右或者向下，从这里我们可以推断出，一个点，它的可能来源只有两个，一个是左边，一个是上面。因此，这里我们的递推式出现了，即到达(i,j)点的路径为到达左边点的路径和到达上边点的路径之和。
递推式如下：a(i,j)=a(i-1,j)+a(i,j-1)

这也是一条自底向上的动态规划的题。

解法

因此下面为这道题的解法代码

#include<iostream>
using namespace std; 
int main()
{
	int horseColumn,horseRow,endColumn,endRow,startRow=2,startColumn=2;
	long long int coord[30][30]={0};//坐标初始化为0.并且将数组的下标范围设置的稍微大一点 
	cin>>endColumn>>endRow>>horseColumn>>horseRow;
	int horse[30][30]={0};
	coord[startColumn][startRow]=1;
	endColumn+=2;
	endRow+=2;
	horseColumn+=2;
	horseRow+=2;
	//统一加上2是为了等一下加加减减的时候不至于越界
	horse[horseColumn-2][horseRow+1]=1;
	horse[horseColumn+2][horseRow+1]=1;
	horse[horseColumn-1][horseRow+2]=1;
	horse[horseColumn+1][horseRow+2]=1;
	horse[horseColumn+2][horseRow-1]=1;
	horse[horseColumn+1][horseRow-2]=1;
	horse[horseColumn-1][horseRow-2]=1;
	horse[horseColumn-2][horseRow-1]=1;
	horse[horseColumn][horseRow]=1;
	//标记马可以走到的位置 
	
	/*
		这里可以推断出递推式
		因为题目中给出只能够走右边或者下边，因此相应的，一个点的位置也只能是上边或者是左边
		这样我们得到递推式：
		coord[i][j]=coord[i-1][j]+coord[i][j-1] 
	*/
	int i=0,j=0;
	for(i=2;i<=endColumn;i++)
	{
		for(j=2;j<=endRow;j++)
		{
			if(horse[i][j]==1)
			{
				continue;
			}
			else
			{
				//if(coord[i][j]<coord[i-1][j]+coord[i][j-1])
					coord[i][j]=coord[i-1][j]+coord[i][j-1];
			}
		}
	}
	cout<<coord[endColumn][endRow];
	return 0;
} 

总结

这道题相对来说还是比较简单，但是需要注意的是它的路径数可能很多，需要申请的范围为long long int
另外，最初我在写这道题的时候比较倾向于用指针来写，但是那样会超过时间，所以最后被舍弃了。