解题思路:

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

方法二:用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;
}


点赞(6)
 

0.0分

2 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 7 条评论

左嘉 6年前 回复TA
@HzuWHF 那么请注意在程序开始处所开辟数组的范围,若要访问下标为20的位置,至少要21行21列
HzuWHF 6年前 回复TA
@HzuWHF @zuojia 噢,我是在别的OJ上测的,数据范围不一样( ॑꒳ ॑ )
左嘉 6年前 回复TA
@HzuWHF 输入应保证所有的数据有解,那么给出的用例:目标B点只可能在棋盘范围内
左嘉 6年前 回复TA
@HzuWHF 请注意读“题目描述”
左嘉 6年前 回复TA
@HzuWHF B点(n, m)(n, m为不超过15的整数)
左嘉 6年前 回复TA
@HzuWHF 输入:一行四个数据,分别表示B点坐标和马的坐标。
HzuWHF 6年前 回复TA
有错, 下面是一组数据
  in :  20 20 4 0
out : 56477364570