马拦过河
【问题描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
【输入】
一行四个数据，分别表示B点坐标和马的坐标。
【输出】
一个数据，表示所有的路径条数。
【样例】
knight.in knight.out
6 6 3 36
【解析】
这是一个看似简单，实则是不那么简单的题，现在我只会简单的方法，等我有空把再把不简单的方法整出来，简单的方法就是递归，款搜、深搜。
递归算法：
pascal代码：
var
n,m,horse_x,horse_y:integer;
k:longint;
i,j:integer;
control:array[-2..17,-2..17] of boolean;
a:array[1..8,1..2] of integer=((-1,-2),(-2,-1),(1,2),(2,1),(-1,2),(2,-1),(-2,1),(1,-2));
procedure try(x,y:integer);
begin
if (x=n) and (y=m) then
begin
inc(k);
exit; end;
if (x+1<=n) and not control[x+1,y] then try(x+1,y);
if (y+1<=m) and not control[x,y+1] then try(x,y+1);
end;
begin
readln(n,m,horse_x,horse_y);
fillchar(control,sizeof(control),0);
k:=0;
for i:=1 to 8 do control[horse_x+a[i,1],horse_y+a[i,2]]:=true;
control[horse_x,horse_y]:=true;
try(0,0);
writeln(k);
end.
C++代码：
#include <iostream>
using namespace std;
int n,m,horse_x,horse_y;
int i,j,k;
int a[8][2]={{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};
bool control[16][16]={0};
void horse(int x,int y)
{
if ((x==n)&&(y==m))
{
++k;
return;
}
if ((x+1<=n) && (!control[x+1][y])) {horse(x+1,y);}
if ((y+1<=m) && !control[x][y+1] ){horse(x,y+1);}
};
int main()
{
cin>>n>>m>>horse_x>>horse_y;
for (i=0;i<8;i++)
{
if ((horse_x+a[i][0]<=n)&&(horse_x+a[i][0]>=0)&&(horse_y+a[i][1]<=m)&&(horse_y+a[i][1]>=0))
control[horse_x+a[i][0]][horse_y+a[i][1]]=true;
}
control[horse_x][horse_y]=true;
horse(0,0);
cout<<k<<endl;
system("pause");
return 0;
}
上面两种写法都是递归，但是两者在细节上处理上有点小不同，如c++代码里的红色那块加了个限制条件，而pascal里没有，那是因为我在pascal里定义control数组时故意把范围扩大了，所以不存在溢出的问题，而c++的下标只能从0开始，所以必须加上红色的限制条件，不然很可能出现数组越界的问题
递归调用的方法，可想而知效率肯定不会理想，但是这个题其实可以优化到n^2！！对了，此题有个条件和经典的动归数字三角形有惊人相似之处“卒行走的规则：可以向下、或者向右”，所以当前状态时有其左边和上边得来，但是有点麻烦的是有个恶心的马，那怎么办呢，简单，直接把这个马的控制点全置为零不就解决问题了吗？？所以动归方程为：f[i][j]=f[i-1][j]+f[i][j-1]，f[i][j]表示从起点能到达（i，j）的路径条数，不过这题要注意要处理边界条件，即当i-1或j-1小于零是的状态，同时f[0][0]=1。代码如下只写了c++代码，
#include <iostream>
using namespace std;
int n,m,horse_x,horse_y;
int i,j,k;
bool flag[16][16];
int a[8][2]={{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};
int f[16][16]={0};
int main()
{
cin>>n>>m>>horse_x>>horse_y;
memset(flag,true,sizeof(flag));
flag[horse_x][horse_y]=false;
for(i=0;i<8;i++)
{
if ((horse_x+a[i][0]<=n)&&(horse_x+a[i][0]>=0)&&(horse_y+a[i][1]>=0)&&(horse_y+a[i][1]<=m))
{
flag[horse_x+a[i][0]][horse_y+a[i][1]]=false;
}
}
f[0][0]=1;
for (i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if (i-1<0&&j-1>=0&& flag[i][j]) f[i][j]=f[i][j-1];
if (i-1>=0&& j-1<0 && flag[i][j]) f[i][j]=f[i-1][j];
if(i-1>=0&&j-1>=0&&flag[i][j]) f[i][j]=f[i-1][j]+f[i][j-1];
}
}
cout<<f[n][m]<<endl;
system("pause");
return 0;
}
虽然时间效率上去了，如果n，m过大的话注意要用高精度，不然……&……