[Jungol] 정올 1106 장기

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30

 Input 

9 9

3 5 2 8

 

 Output 

2 

아래와 같이 말을 움직이면 2번에 졸을 잡을 수 있습니다.

① 말이 움직이는 방향은 8가지 입니다.

② visited[][] 배열을 초기에 임의의 큰 수로 초기화 한 후,

    BFS 탐색하면서 최소 움직임으로 방문한 횟수를 저장합니다.

    (즉, visited[][]에는 더 적은 움직임 횟수를 재방문 허용)

③ 졸이 위치한 좌표가 ex, ey일 때, visited[ex][ey] 출력

 

---

#include <stdio.h>
const int INF = 2e9;
const int MAX_NM = 100 + 5;
const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int N, M;
int sx, sy, ex, ey;
int visited[MAX_NM][MAX_NM];
struct Node{
    int x, y, cost;
}que[MAX_NM * MAX_NM * 8];
int fr, re;
 
void init() {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            visited[i][j] = INF;
        }
    }
}
 
void BFS() {
    que[re++] = { sx, sy, 0 };
    visited[sx][sy] = 0;
    while (fr < re) {
        Node cur = que[fr++];
 
        if (cur.x == ex && cur.y == ey) {
            continue;
        }
 
        for (int i = 0; i < 8; ++i) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            if (nextX < 1 || nextY < 1 || nextX > N || nextY > M)
                continue;
            
            int nextCost = cur.cost + 1;
            if (visited[nextX][nextY] <= nextCost) continue;
 
            visited[nextX][nextY] = nextCost;
            que[re++] = { nextX, nextY, nextCost };
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
 
    init();
    BFS();
    printf("%d\n", visited[ex][ey]);
}