P146 A Knight's Journey

DFS 含递归
这么写会超时，不知道为啥。

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

using namespace std;

const int MAXN = 30;

int p, q;
bool visit[MAXN][MAXN];
int dir[8][2] = {
{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}
};

int DFS(int x, int y, int step, string ans){
    if(step == p * q){
        cout << ans << endl;
        return true;
    }else{
        for(int i = 0; i < 8; ++i){  //遍历邻居节点 
            int nx = x + dir[i][0];  //扩展状态坐标 
            int ny = y + dir[i][1];
            char col = ny + 'A';  //该点编号 
            char row = nx + '1';
            if(nx < 0 || nx >= p || ny < 0 || ny >= q || visit[nx][ny]){
                continue;
            }
            visit[nx][ny] = true; //标记该点 
            if(DFS(nx, ny, step + 1, ans + col + row)){
                return true;
            }
            visit[nx][ny] = false; //取消标记 
        }
    }
    return false;
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> p >> q;
        memset(visit, false, sizeof(visit));
        printf("Scenario #%d:\n", i);
        visit[0][0] = true;
        if(!DFS(0, 0, 1, "A1")){
            cout << "impossible" << endl ;
        }
        cout << endl;
    }
    return 0; 
}

把输入时的循环改了一下，AC了

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

using namespace std;

const int MAXN = 30;

int p, q;
bool visit[MAXN][MAXN];
int dir[8][2] = {
{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}
};

int DFS(int x, int y, int step, string ans){
    if(step == p * q){
        cout << ans << endl;
        return true;
    }else{
        for(int i = 0; i < 8; ++i){  //遍历邻居节点 
            int nx = x + dir[i][0];  //扩展状态坐标 
            int ny = y + dir[i][1];
            char col = ny + 'A';  //该点编号 
            char row = nx + '1';
            if(nx < 0 || nx >= p || ny < 0 || ny >= q || visit[nx][ny]){
                continue;
            }
            visit[nx][ny] = true; //标记该点 
            if(DFS(nx, ny, step + 1, ans + col + row)){
                return true;
            }
            visit[nx][ny] = false; //取消标记 
        }
    }
    return false;
}

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