나이트의 이동

BFS


출처: BOJ 나이트의 이동

SOL)
BFS 범위 생각해서 방문한 위치가 아니면 간다.


[-] Collapse

#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;

bool board[1000][1000];
int T;
int sx, sy;
int fx, fy;

int dx[8] = { 2, 2, 1, -1, -2, -2, -1, 1 };
int dy[8] = { -1, 1, 2, 2, 1, -1, -2, -2 };

int main(){
    freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while (T--){
        memset(board, false, sizeof(board));
        int ans = 0;
        int len;
        scanf("%d %d %d %d %d",&len, &sx, &sy, &fx, &fy);
        queue<pair<pair<int, int>, int> > mq;
        mq.push(make_pair(make_pair(sx, sy), 0));
        board[sx][sy] = true;
        bool check = false;
        while (!mq.empty()){
            int size = mq.size();
            for (int i = 0; i < size; i++){
                if (check) break;
                int x = mq.front().first.first;
                int y = mq.front().first.second;
                mq.pop();
                if (x == fx && y ==fy) {
                    printf("%d\n", ans);
                    check = true;
                    break;
                }
                for (int i = 0; i < 8; i++){
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < len && ny <len && !board[nx][ny]){
                        mq.push(make_pair(make_pair(x + dx[i], y + dy[i]), ans + 1));
                        board[nx][ny] = true;
                    }
                }
            }
            if (check) break;
            ans++;
        }

    }
}