首页 > > 程序设计 > C/C++ >

POJ 2488 A Knight's Journey (DFS)

2018-06-17 23:56:01来源：未知阅读 ()

题目给出棋盘的尺寸，骑士随便从哪出发，且只能走“日”字。不经过重复的点走完，结果按字典序输出。因为A1字典序最小，所以所求的路径一定是从A1开始的。

输出没冒号，入坑WA了几次。以后多注意。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int a,b;
bool visit[30][30];
char path[30][5];
int dx[10]= {-1,1,-2,2,-2,2,-1,1}; //8个方向，已按字典序拍好
int dy[10]= {-2,-2,-1,-1,1,1,2,2};

bool dfs(int x,int y,int num)
{
    if(num==a*b)
        return true;
    for(int i=0;i<8;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>0 && nx<=a && ny>0 && ny<=b && visit[nx][ny]==false)
        {
            path[num+1][0]=nx+'0';
            path[num+1][1]=ny+'A'-1;
            visit[nx][ny]=true;
            if(dfs(nx,ny,num+1))
                return true;
            visit[nx][ny]=false;
        }
    }
    return false;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
    {
        scanf("%d%d",&a,&b);
        memset(visit,0,sizeof(visit));
        memset(path,0,sizeof(path));
        path[1][0]='1';
        path[1][1]='A';
        visit[1][1]=true;
        printf("Scenario #%d:\n",j);
        if(dfs(1,1,1))
            for(int i=1;i<=a*b;i++)
                printf("%c%c",path[i][1],path[i][0]);
        else
            printf("impossible");
        printf("\n\n");
    }
    return 0;
}