poj 2488 A Knight's Journey(DFS)

 

Memory: 172 Time:0MS

解题思路

题意：

    一个骑士无聊了，于是进行世界旅行，他的世界是一个矩形棋盘，当他移动的时候，先向一个方向走两个，再在垂直的方向上走一格，不能走出棋盘，我们的任务是找到一条路径，骑士走遍所有的格子，每个走一次，如果有那么一条路，把路径输出，横坐标按字母表顺序从小到大，纵坐标按数字顺序从小到大。如果没有输出“impossible”。

 

思路：

   骑士每次行走都有八个方向可走，把八个坐标按题所要求的顺序存在数组dir里，dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}} ，然后深搜的时候一个一个搜，如果当前一步走出了棋盘或者是已经走过的路就回溯。每往前走一步把格子的坐标用path[]记录下来。

源程序

 

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 50
#define M 2*N*N+10

int dir[8][2] = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
int count = 0, flag, h, v;
int g[N][N];
char path[M];

int ok(int i, int x, int y)
{
    if(x + dir[i][0] > 0 && x + dir[i][0] <= h && y + dir[i][1] > 0 && y + dir[i][1] <= v && !g[x+dir[i][0]][y+dir[i][1]])
        return 1;
    else
        return 0;
}

void dfs(int x, int y)
{
    int i;
    if(flag)
        return;
    g[x][y] = 1;
    path[count++] = x + 'A' - 1;
    path[count++] = y + '0';
    if(count == h * v * 2)
    {
        flag = 1;
        return ;
    }
    for(i=0; i<8; i++)
    {
        if(ok(i, x, y) && !flag)
        {
            dfs(x + dir[i][0], y + dir[i][1]);
            count -= 2;
            g[x+dir[i][0]][y+dir[i][1]] = 0;
        }
    }
}

int main()
{
    int t, k=0, i, j;
    
    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &v, &h);
        for(i=1; i<=v; i++)
            for(j=1; j<=h; j++)
                g[i][j] = 0;
        k++;
        printf("Scenario #%d:\n", k);
        count = 0;
        memset(path, 0, N*N*2);

        flag = 0;   //本来没设flag，死活得不到正解，后来同学的帮助下才发现了原来是这个问题，但是他也说不清为什么这么设个flag。如果有知道的请告诉我下。
        dfs(1, 1);
        if(flag)
            printf("%s", path);
        else printf("impossible");
        printf("\n\n");
    }
    getch();
    return 0;
}