[16948] 데스 나이트

https://www.acmicpc.net/problem/16948

16948번: 데스 나이트

<문제>

방향데이터는 입력에서 주어진 6개를 순서대로 구성하면 된다.

편의상 큐에넣는 state는 {행, 열, 거리}순으로 구성해주었고, bfs를 사용해서 구현해주었다

최적해를 묻는 정형화된 bfs와 다른점은 방향데이터의 구성 딱 한 가지뿐이다.

그 외에는 다른 bfs와 다른 것이 없다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int y, x, turn;
} state;
int sy, sx, ey, ex, n, dy[6] = {-2, -2, 0, 0, 2, 2},
                       dx[6] = {-1, 1, -2, 2, -1, 1};
void f(void) {
    queue<state> q;
    q.push({sy, sx, 0});
    int i;
    bool visited[201][201] = {0};
    visited[sy][sx] = true;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == ey && cur.x == ex) {
            cout << cur.turn;
            return;
        }
        for (i = 0; i < 6; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= n) continue;
            if (visited[y][x]) continue;
            q.push({y, x, cur.turn + 1});
            visited[y][x] = true;
        }
    }
    cout << "-1";
}
int main(void) {
    cin >> n;
    cin >> sy >> sx >> ey >> ex;
    f();
    return 0;
}