本文共 1153 字，大约阅读时间需要 3 分钟。

题目描述：

棋盘上AAA点有一个过河卒，需要走到目标BBB点。卒行走的规则：可以向下、或者向右。同时在棋盘上CCC点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AAA点(0,0)(0, 0)(0,0)、BBB点(n,m)(n, m)(n,m)(nnn, mmm为不超过202020的整数)，同样马的位置坐标是需要给出的。

#输入格式

一行四个数据，分别表示BBB点坐标和马的坐标。

输出格式

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

输入输出样例

输入 #1

6 6 3 3

输出 #1

6

说明/提示

结果可能很大！

心得：做这个题的时候以为就是简单的深搜，最后交的时候时间超限，数据太大了，最后发现是dp动态规划，就是如果该点是马能到的位置就不记录，否则就依次去累加两个方向到的位置。

程序代码：

#include
   
    #include
    
     using namespace std; long long a[200][200],f[200][200];int main(){
   		int nect[8][2]={
   {
   1,2},{
   2,1},{
   2,-1},{
   1,-2},{
   -2,-1},{
   -1,-2},{
   -2,1},{
   -1,2}};	int i,j,t1,t2,t3,n,m,t4;	f[1][1]=1;	scanf("%d%d%d%d",&n,&m,&t3,&t4);	n++;m++;t3++;t4++;	for(i=1;i<=n;i++)		for(j=1;j<=m;j++)			a[i][j]=0;	for(i=0;i<8;i++)	{
    		t1=t3+nect[i][0];		t2=t4+nect[i][1];		if(t1<0||t1>n||t2<0||t2>m)			continue;		a[t1][t2]=1;	}	a[t3][t4]=1;	for(int i=1;i<=n;i++)	{
           for(int j=1;j<=m;j++)		{
               if(a[i][j])				continue;            f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]);     	}    }   // printf("%lld\n",f[7][5]);	printf("%lld\n",f[n][m]);	return 0;}
    
   

转载地址：http://xexzi.baihongyu.com/