| 等 级 | |
| 排 名 | 5 |
| 经 验 | 34534 |
| 参赛次数 | 226 |
| 文章发表 | 72 |
| 年 龄 | 40 |
| 在职情况 | 在职 |
| 学 校 | 北京理工大学 |
| 专 业 |
自我简介：
TA的其他文章
| Dinner-题解（C++代码） 浏览：506 |
| 信息学奥赛一本通T1444-埃及分数-题解（C语言代码） 浏览：583 |
| 用Python爬取本站离线题库 浏览：778 |
你可能喜欢
人见人爱A+B （C语言代码）浏览：1046 |
母牛的故事 （C语言代码）浏览：1748 |
简单的a+b （C语言代码）浏览：528 |
求圆的面积 （C语言代码）浏览：1366 |
printf基础练习2 （C语言代码）浏览：690 |
原题链接：马拦过河卒
解题思路:
方法一：卒可以向右、向下寻找路径，若路径可达，递归探索下一步，若达到目标点，增加一条路径。
方法二：用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分
19 人评分
左嘉 2018-08-22 21:49:33 |
输入：一行四个数据，分别表示B点坐标和马的坐标。
左嘉 2018-08-22 21:49:50 |
B点(n, m)(n, m为不超过15的整数)
左嘉 2018-08-22 21:51:30 |
请注意读“题目描述”
左嘉 2018-08-22 21:54:43 |
输入应保证所有的数据有解，那么给出的用例：目标B点只可能在棋盘范围内
HzuWHF 2018-08-22 22:57:02 |
@zuojia 噢，我是在别的OJ上测的，数据范围不一样( ॑꒳ ॑ )
左嘉 2018-08-23 21:46:11 |
那么请注意在程序开始处所开辟数组的范围，若要访问下标为20的位置，至少要21行21列