王道机试指南 例题9.3 Knight's Journey

题目:

题目大意:

日字规则:

这个棋字的行走规则是“日”字,就是说它可以跳到“日”字对角线的位置,如果有对方的棋字,那么就可以“吃”掉。如下图,黄色是自己的马,那么绿色就是可以行走的位置。

算法及思路:

代码:

#include <iostream>
#include <string>
#include <cstring> //memset函数的头文件

using namespace std;

const int MAXN=30;
int p,q;
bool visit[MAXN][MAXN];
int direction[8][2]={{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};//保存日字规则下下一步的八种走法

bool DFS(int x,int y,int step,string ans){//深度优先搜索
    if(step==p*q){//如果当前步数==p*q,则搜索成功
        cout<<ans<<endl;
        cout<<endl;
        return true;
    }
    else{//否则继续搜索
        for(int i=0;i<8;i++){//依次将日字规则下下一步的八种情况按深度优先搜索规则进行遍历
            int nx=x+direction[i][0];
            int ny=y+direction[i][1];
            char col=ny+'A';//列号
            char row=nx+'1';//行号
            if(nx<0 || nx>=p || ny<0 || ny>=q || visit[nx][ny]==1)//如果下一步走出棋盘边界或已经走过,则讨论下一种情况
                continue;
            visit[nx][ny]= true;//标记位置
            if(DFS(nx,ny,step+1,ans+col+row)==1)//如果遍历成功则返回
                return true;
            else//否则取消标记
                visit[nx][ny]=false;
        }
    }
    return false;
}

int main(){
    int n;
    cin>>n;
    int caseNum=1;
    for(int i=0;i<n;i++){
        cin>>p>>q;
        memset(visit,false, sizeof(visit));
        cout<<"Scenario #"<<caseNum++<<":"<<endl;
        visit[0][0]=true;//标记设置A1位置为访问过
        if(DFS(0,0,1,"A1")==0) {//深度优先搜索
            cout << "impossible" << endl;
            cout<<endl;
        }
    }
    return 0;
}

运行结果:

全部评论
给大佬送上一大束玫瑰花
点赞 回复 分享
发布于 2023-02-13 09:36 辽宁
谢谢楼主的解答
点赞 回复 分享
发布于 2023-02-13 09:27 四川

相关推荐

10-02 19:29
已编辑
浙江科技大学 运营
点赞 评论 收藏
分享
评论
点赞
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务