BOJ 7562 나이트의 이동 편집하기

==개요==
[[분류: 그래프 이론]]
[[분류: 그래프 탐색]]
[[분류: 너비 우선 탐색]]
{{BOJ|단계=31}}

==C++==
<syntaxhighlight lang='cpp'>
#include <bits/stdc++.h>
using namespace std;

int T, I;
int sx, sy;
int ox, oy;
int visited[300][300];

void bfs() {
    int x, y, nx, ny;
    for(x=0; x<I; x++) {
        for(y=0; y<I; y++) {
            visited[x][y] = 0;
        }
    }
    queue<pair<int,int>> q;
    q.push({sx, sy});
    visited[sx][sy] = 1;
    
    int dx[8] = {1, 2,  2,  1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2, -2, -1,  1,  2};

    pair<int,int> p;
    while(!q.empty()) {
        p = q.front();
        q.pop();
        x = p.first;
        y = p.second;
        for(int i=0; i<8; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if(nx<0 || nx>=I || ny<0 || ny>=I || visited[nx][ny]>0) continue;
            q.push({nx, ny});
            visited[nx][ny] = visited[x][y]+1;
            if(nx == ox && ny == oy) return;
        }
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &I);
        scanf("%d %d", &sx, &sy);
        scanf("%d %d", &ox, &oy);
        bfs();
        printf("%d\n", visited[ox][oy]-1);
    }
}
</syntaxhighlight>