左嘉


私信TA

用户名:zuojia

访问量:70461

签 名:

Jz

等  级
排  名 3
经  验 31214
参赛次数 226
文章发表 72
年  龄 36
在职情况 在职
学  校 北京理工大学
专  业

  自我简介:

解题思路:

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

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


 

0.0分

18 人评分

  评论区

有错, 下面是一组数据
  in :  20 20 4 0
out : 56477364570
2018-08-21 23:31:54 | |
  • «
  • 1
  • »