[7562] 나이트의 이동

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

7562번: 나이트의 이동

<문제>

방향데이터를 나이트에 맞게 변경해주고, bfs를 수행하면 된다.

 

나이트의 이동방법, 비숍의 이동방법...등 은근히 체스와 관련한 문제가 많이 나온다. 

어떤 기물이냐에 따라 주로 나오는 문제의 스타일이 다른것도 재미있는 부분,

보통은 수학/조합론/정수론/그래프 탐색에 연관된게 많다.

 

<소스코드>

#include <stdio.h>
 
#include <queue>
using namespace std;
#define INF 12345
int n, sy, sx, ey, ex, a[301][301], dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2},
                                    dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
queue<int> q;
int f(void) {
    int i, j, y, x, ty, tx;
    q.push(sy);
    q.push(sx);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) a[i][j] = INF;
    a[sy][sx] = 0;
    while (!q.empty()) {
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i <= 7; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (x >= 0 && y >= 0 && x < n && y < n && a[y][x] == INF) {
                q.push(y);
                q.push(x);
                if (a[y][x] > a[ty][tx] + 1) a[y][x] = a[ty][tx] + 1;
            }
        }
    }
    return a[ey][ex];
}
int main(void) {
    int t, i, j;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d", &n);
        scanf("%d %d", &sy, &sx);
        scanf("%d %d", &ey, &ex);
        printf("%d\n", f());
    }
    return 0;
}