poj2488 A Knight's Journey 骑士周游问题 BFS 王道P148 todo

//poj2488  A Knight's Journey  骑士周游问题 BFS 王道P148 todo
//http://poj.org/problem?id=2488
//没搞明白算法  而且 OJ报粗 编译错误  todo
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
int direction[8][2] = { //todo
        {-1,-2},{1,-2},{-2,-1},{2,-1},
        {-2,1},{2,1},{-1,2},{1,2}
};
const int MAXN = 30;
bool visit[MAXN][MAXN];



bool DFS(int x,int y,int step,string answer,int p,int q){
    if(step == p*q){
        cout << answer << endl << endl;
        return true;
    }
    for(int i=0;i<8;++i){
        int nx = x + direction[i][0];
        int ny = y + direction[i][1];

        if(nx < 0 || nx >=p || ny<0 || ny>=q || visit[nx][ny]){
            continue;
        }
        visit[nx][ny] = true;
        char col = ny + 'A';
        char row = nx + '1';
        if(DFS(nx,ny,step+1,answer+col+row,p,q)){
            return true;
        }
        visit[nx][ny] = true;

    }
    return false;
}

int main(){
    int n;
    int caseNumber = 0;
    scanf("%d",&n);
    while(n--){
        int p,q;
        scanf("%d%d",&p,&q);
        memset(visit, false,sizeof(visit));
        cout<<"Scenario #"<<++caseNumber<<":"<<endl;
        visit[0][0] = true;
        if(DFS(0,0,1,"A1",p,q)){
            continue;
        }else{
            cout<<"impossible"<<endl<<endl;
        }
    }

    return 0;
}