DFS poj2488 A Knight's Journey

2049 단어
고전적인 검색 + 최소 사전 순서 경로 인쇄
마지막 노드의 위치를 저장하고 마지막으로 내보내기 위해 LAST 구조체를 교묘하게 활용
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MX = 30;
const int INF = 0x3f3f3f3f;

int m, n;
bool vis[MX][MX];
int dist[][2] = {{ -1, -2}, {1, -2}, { -2, -1}, {2, -1}, { -2, 1}, {2, 1}, { -1, 2}, {1, 2}};

struct LAST {
    int x, y;
} La[MX][MX], End;

bool DFS(int x, int y, int cnt) {
    if(cnt == m * n) {
        End.x = x;
        End.y = y;
        return true;
    }

    vis[x][y] = 1;
    for(int k = 0; k < 8; k++) {
        int nx = x + dist[k][0], ny = y + dist[k][1];

        if(nx < 1 || nx > m || ny < 1 || ny > n) continue;
        if(vis[nx][ny]) continue;

        La[nx][ny].x = x;
        La[nx][ny].y = y;
        if(DFS(nx, ny, cnt + 1)) {
            vis[x][y] = 0;
            return true;
        }
    }
    vis[x][y] = 0;
    return false;
}

void print(int x, int y, int cnt) {
    if(cnt == m * n) {
        return;
    }

    print(La[x][y].x, La[x][y].y, cnt + 1);

    printf("%c%d", 'A' + y - 1, x);
    if(!cnt) printf("
"); } int main() { int T, ansk = 0; scanf("%d", &T); while(T--) { memset(vis, false, sizeof(vis)); End.x = -1; scanf("%d%d", &m, &n); bool sign = false; for(int j = 1; j <= n; j++) { for(int i = 1; i <= m; i++) { if(DFS(i, j, 1)) { sign = true; break; } } if(sign) break; } printf("Scenario #%d:
", ++ansk); if(End.x != -1) { print(End.x, End.y, 0); } else { printf("impossible
"); } printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기