无马情况
#include <iostream>
// 定义棋盘大小
#define MAXSIZE 30
using namespace std;
int main(){
int a[MAXSIZE][MAXSIZE]={0};
int n,m; // n,m为B点的坐标,A点默认为(0,0)
cin >> n >> m;
for (int i=0;i<=n;i++){
for (int j=0;j<=m;j++){
if (i==0 && j==0){
continue; // A点
}
if (i==0 || j==0){
a[i][j]=1; // 边上的点都设置为1步
}
else {
a[i][j]= a[i-1][j] + a[i][j-1]; // 类似于杨辉三角
}
}
}
cout << a[n][m]; // 输出B点步数
return 0;
}
有马情况
#include <iostream>
// 定义棋盘大小
#define MAXSIZE 30
using namespace std;
int main(){
int a[MAXSIZE][MAXSIZE]={0};// 默认为0
int n,m,x,y; // n,m为B点的坐标,A点默认为(0,0)。x,y为马的坐标
cin >> n >> m >> x >> y;
// A到B范围内初始化为1
for (int i=0;i<=n;i++){
for (int j=0;j<=m;j++){
a[i][j]=1;
}
}
// 标记马和马控制的点为0
a[x][y]=0;
if (x+2<=n && y-1>=0){a[x+2][y-1]=0;}
if (x+2<=n && y+1<=m){a[x+2][y+1]=0;}
if (x+1<=n && y+2<=m){a[x+1][y+2]=0;}
if (x-1>=0 && y+2<=m){a[x-1][y+2]=0;}
if (x-2>=0 && y+1<=m){a[x-2][y+1]=0;}
if (x-2>=0 && y-1>=0){a[x-2][y-1]=0;}
if (x-1>=0 && y-2>=0){a[x-1][y-2]=0;}
if (x+1<=n && y-2>=0){a[x+1][y-2]=0;}
for (int i=0;i<=n;i++){
for (int j=0;j<=m;j++){
if (i==0 && j==0){
continue; // A点
}
if (a[i][j]==0){
continue;
}
if (i==0){
a[i][j]=a[i][j-1]; // 竖边
}
else if (j==0){
a[i][j]= a[i-1][j]; // 横边
}
else {
a[i][j]= a[i-1][j] + a[i][j-1]; // 类似于杨辉三角
}
}
}
cout << a[n][m]; // 输出B点步数
return 0;
}
在考虑马的情况下,对于竖边和横边来说,需要让他们等于对应的上边一个和对应的左边一个,这样就可以计算出马挡住的格子。由于一开始判断a[i][j]==0
,所以无需担心马的控制范围或马自身被覆盖。
洛谷:https://www.luogu.com.cn/problem/P1002
注意,在刷题网站上要多考虑一步数组的数据类型,最好用long long,然后注意数组的范围,可以给数据和循环起始条件+2。
© 版权声明
若无特殊说明,文章版权归作者所有,请勿转载至任何平台。
THE END
暂无评论内容