【C++】过河卒问题

无马情况

#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。

感谢视频:https://www.bilibili.com/video/BV1FC4y1E7BD

© 版权声明
THE END
点赞14 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片快捷回复

    暂无评论内容