poj 2488 A Knight's Journey(DFS)

╰半夏微凉° 2022-08-05 08:52 101阅读 0赞

题目大意：给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。

马的遍历是一道经典回溯题，当然还是DFS...这题有2个要密切注意的地方：

1、题目要求以字典序方式输出，要以字典序输出路径，那么方向数组就要以特殊的顺序排列了,这样只要每次从dfs(0,0)开始搜索，第一个成功遍历的路径一定是以字典序排列.

2、国际象棋的棋盘，横行为字母，表示横行坐标的是y；纵行为数字，表示纵行的坐标是x...一开始又搞反了...

#include <iostream>
    #include <cmath>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    
    using namespace std;
    
    int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};   //记录方向
    int g,a,b;//g用来记录是否找到解，找到后不再搜索
    int vist[26][26],path[26][2];
    
    void find(int i,int j,int k)//i,j是要走的格子，k记录已经走过的步数
    {
        if(k==a*b)//走完了
        {
            for(int i=0;i<k;i++)
                printf("%c%d",path[i][0]+'A',path[i][1]+1);
            printf("\n");
            g=1;
        }
        else
        {
            for(int x=0;x<8;x++)//8个方向依次搜索
            {
                int n=i+dir[x][0];
                int m=j+dir[x][1];
                if(n>=0&&n<b&&m>=0&&m<a&&!vist[n][m]&&!g)
                {
                    vist[n][m]=1;//标记已走
                    path[k][0]=n,path[k][1]=m;
                    find(n,m,k+1);
                    vist[n][m]=0;//清除标记
                }
            }
        }
    }
    
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int m=0;m<n;m++)
        {
            g=0;
            scanf("%d %d",&a,&b);
            for(int i=0;i<a;i++) //初始化
                for(int j=0;j<b;j++)
                    vist[i][j]=0;
            vist[0][0]=1;
            path[0][0]=0,path[0][1]=0;
            printf("Scenario #%d:\n",m+1);
            find(0,0,1);
            if(!g) printf("impossible\n");
            printf("\n");
        }
        return 0;
    }