王道机试指南 例题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;
}

运行结果：