POJ 2488 A Knight's Journey (DFS)

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

新老客户大回馈,云服务器低至5折

题目给出棋盘的尺寸,骑士随便从哪出发,且只能走“日”字。不经过重复的点走完,结果按字典序输出。因为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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:POJ 3026 Borg Maze 广搜(BFS)+最小生成树

下一篇:使用zookeeper实现分布式master选举(c 接口版本)