博客

棋盘上A点有一个过河卒，需要走到目标B点。小兵行走的规矩是：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

棋盘用坐标表示，A点（0.0），B点（n.m）,马的坐标位置是需要给出的

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

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

输出为一个整数，表示所有的路径条数

题解

初始位置是从（0.0）开始的，不方便我们解题，把题里坐标都加一,初始位置从（0.0）变成（1.1）。

考虑没有马的限制，小兵可以向右向下走，可以想到，一个小兵只能从当前格子的左侧格子和当前格子的上方格子走到当前格子。

假设从(1.1)走到当前格子的左侧格子的路径条数为x，从(1.1)走到当前格子的上方格子的路径条数为y，那么从(1.1)走到当前格子的路径条数就应该是x+y。

观察可得动态规划的转移方程，设f(i,j)表示从(1.1)格子走到当前格子的路径条数

那么可以得出

f(i,j)=f(i-1,j)+f(i,j-1)

(i,j)是当前格子，那么（i-1,j）就是左侧格子，(i,j-1)就是当前格子的上方格子。

我们只需要从小到大依次 枚举 i和j就能获得所有点的答案，可以想到，在这道题里我们要求的是f(n,m) 即到B(n,m)的路径条数

如果只是按照这个公式推，因为f的初始数值为0，再怎么推也是0，我们要让f(1.1)能够根据上面得到的式子推出答案是1，这样才能有意义。

根据f(1.1)=f(0.1)+f(1.0)

我们只需要让f(0.1)=1或者f(0.1)=1即可。

接下来考虑加了马的问题，假设（a.b）这个点被马给挡住了，其实就是说这个点小兵不能走到，那么当我们枚举到这个点时，那我们就跳过这个点，让f(a,b)=0即可

写代码时 我们要注意判断一个点有没有被马拦住，会用到(i-2,j-1)和(i-1,j-2)这两个位置，那如果不把所有的点的坐标都加上2，就会因为数组越界而挖掉一个点

答案可能比较大，使用long long

具体代码如下

#include<iostream>
#include<string>
#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, nx, my;
ll lj[40][40];
bool s[40][40];//判断这个点能不能走

int main()
{
	//c scanf输入数据 printf输出数据
	cin >> bx >> by >> nx >> my;
	bx += 2; by += 2; nx += 2; my += 2;
	lj[1][2] = 1;//初始化让lj[2][2]=1；
	s[nx][my] = 1;
	for (int i = 1; i <= 8; i++)
	{
		s[nx + 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;//lj[i][j] = 0;
			}
			lj[i][j] = lj[i - 1][j] + lj[i][j - 1];
		}
	cout << lj[bx][by] << endl;
	//return 0;
}