(백준) 7562 기사의 움직임

문제 설명

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

기사가 보드에 배치되고 기사가 한 번에 이동할 수 있는 사각형이 주어지면 기사가 해당 사각형으로 몇 번 이동할 수 있는지 알아보십시오.

문제를 풀다

최단 거리를 찾는 문제이므로 bfs를 사용하여 해결할 수 있습니다.

1차원적 숨바꼭질과 달리 2차원적일 뿐인 백준 1697호 숨바꼭질과 비슷한 문제다.

먼저 기사가 움직일 수 있는 범위는 다음과 같다.

• (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (이십 일)

기사 이동 횟수를 포함하는 배열 arr을 선언하고 -1로 초기화합니다.

큐가 비워질 때까지 while 문을 반복하는 기존 bfs 문제와 달리 이 문제는 해당 위치에 값이 들어갈 때 while 문을 종료합니다.

대기열에서 현재 말이 있는 사각형을 시작점으로 하고 while문을 실행하여 이동 횟수를 동시에 업데이트합니다.

while 문이 끝나면 해당 셀에 값을 출력합니다.

소스 코드

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int t, n;

int x, y, x2, y2;

int arr(301)(301);

int dy(8) = { -2, -2, -1, -1, 1, 1, 2, 2 };
int dx(8) = { -1, 1, -2, 2, -2, 2, -1, 1 };

int main()
{
    cin >> t;
    
    while (t--)
    {
        cin >> n;
        cin >> x >> y;
        cin >> x2 >> y2;
    
        for (int i = 0; i < n; i++)
            fill(arr(i), arr(i) + n, -1);
            
        queue<pair<int, int>> q;
        q.push({y, x});
        
        arr(y)(x) = 0;
        
        while (arr(y2)(x2) == -1)
        {
            int yy = q.front().first;
            int xx = q.front().second;
            
            q.pop(); 
            
            for (int i = 0; i < 8; i++)
            {
                int ny = yy + dy(i);
                int nx = xx + dx(i);
                
                if (ny < 0 || nx < 0 || ny >= n || nx >= n)
                    continue;
                if (arr(ny)(nx) != -1)
                    continue;
                arr(ny)(nx) = arr(yy)(xx) + 1;
                q.push({ny, nx});
            }
        }
        printf("%d\n", arr(y2)(x2));
    }
    return 0;
}