马拦过河卒 （C语言代码）

解题思路:

方法一：卒可以向右、向下寻找路径，若路径可达，递归探索下一步，若达到目标点，增加一条路径。

方法二：用g[x][y]记录棋盘的状态，每个位置默认状态为0，卒可以经过；马所在位置以及马可达的8个位置状态为1，不允许卒经过。用f[i][j]记录从点(0,0)到点(i,j)的路径条数，根据卒行走的规则，f[0][0]为1，当j==0，棋盘数组第一列f[i][0]=f[i-1][0]，当i==0，棋盘数组第一行f[0][j]=f[0][j-1]；当i属于[1,n]、j属于[1,m]，f[i][j]=f[i-1][j]+f[i][j-1]。

注意事项:
卒只能向右或向下走，不能后退，每走一步，其行号或列号只会增加。

参考代码:

方法一：

#include<stdio.h>
int n,m,hx,hy,c=0;
int a[18][18]={0};
int main(){
	int i;
	void hloc();
	void backtrack(int,int);
	scanf("%d%d%d%d",&n,&m,&hx,&hy);
	hloc();//在马的影响下棋盘的状态
	for(i=0;i<=m+2;i++){
		a[0][i]=1;
		a[n+2][i]=1;
	}//设置上下边框不可达
	for(i=0;i<=n+2;i++){
		a[i][0]=1;
		a[i][m+2]=1;
	}//设置左右边框不可达
	backtrack(1,1);//从边框内的原点开始探索路径
	printf("%d",c);
	return 0;
}
void hloc(){
	int i,new_x,new_y;
	int x[8]={-2,-1,1,2,2,1,-1,-2};
	int y[8]={1,2,2,1,-1,-2,-2,-1};
	a[hx+1][hy+1]=1;//马所在位置标记为1
	for(i=0;i<8;i++){
		new_x=hx+x[i]+1;
		new_y=hy+y[i]+1;
		if(new_x>=1&&new_x<=n+1&&new_y>=1&&new_y<=m+1)
			a[hx+x[i]+1][hy+y[i]+1]=1;
	}//马可达的8个控制点标记为1
}
void backtrack(int x,int y){
	int i;
	int xx[2]={0,1};
	int yy[2]={1,0};
	if(x==n+1&&y==m+1){//若达到目标点
		c++;//增加一条路径
		return;
	}
	for(i=0;i<2;i++)//卒可以向右、向下寻找路径
		if(a[x+xx[i]][y+yy[i]]==0)//若路径可达
			backtrack(x+xx[i],y+yy[i]);//探索下一步
}

方法二：

#include<stdio.h>
int main(){
	int i,j,n,m,x,y;
	int g[20][20]={0};
	int f[20][20]={0};
	int dx[8]={-2,-1,1,2,2,1,-1,-2};
	int dy[8]={1,2,2,1,-1,-2,-2,-1};
	scanf("%d%d%d%d",&n,&m,&x,&y);
	g[x][y]=1;//马所在的位置状态为1
	for(i=0;i<8;i++)
		if(x+dx[i]>=0&&x+dx[i]<=n&&y+dy[i]>=0&&y+dy[i]<=m)
			g[x+dx[i]][y+dy[i]]=1;//马可达的8个位置状态为1
	f[0][0]=1;//初始化可达原点的路径数
	for(i=1;i<=n;i++)
		if(g[i][0]==0) f[i][0]=f[i-1][0];//初始化第一列的路径数
	for(j=1;j<=m;j++)
		if(g[0][j]==0) f[0][j]=f[0][j-1];//初始化第一行的路径数
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(g[i][j]==0)//若可达，从两个可能方向继承前一步的路径数
				f[i][j]=f[i-1][j]+f[i][j-1];
	printf("%d",f[n][m]);
	return 0;
}