[백준] 16948번 데스 나이트

 

[적용한 알고리즘]

BFS

 

[아이디어]

BFS

 

[생각의 흐름 / 절차] 

X

 

[교훈]

X

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

typedef struct{
    int x;
    int y;
} cord;

int n;
int StartX, StartY;
int EndX, EndY;
bool visited[201][201];
queue<cord> q;
int dist[201][201];
int dirx[] = {-2, -2, 0, 0, 2, 2};
int diry[] = {-1, 1, -2, 2, -1, 1};

bool inChess(int x, int y){
    if (0 <= x && x < n && 0 <= y && y < n) return true;
    return false;
}
void bfs(){
    while (!q.empty()){
        int curx = q.front().x;
        int cury = q.front().y;
        q.pop();

        for (int i = 0; i < 6; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inChess(nx, ny)){
                if (!visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                    dist[nx][ny] = dist[curx][cury] + 1;
                }
            }
        }
    }
}
int main(){
    scanf("%d", &n);
    scanf("%d %d %d %d", &StartX, &StartY, &EndX, &EndY);

    q.push({StartX, StartY});
    visited[StartX][StartY] = true;
    bfs();

    if (!visited[EndX][EndY]){
        printf("-1\n");
    }
    else {
        printf("%d\n", dist[EndX][EndY]);
    }
    return 0;
}