백준 #7562

나이트의 이동 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

36058

17890

13366

48.666%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2001 3번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: sait2000
• 문제의 오타를 찾은 사람: sgchoi5

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

 

 

 

 

---

import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def bfs(start, destination):

    d_lst = [[1, 2], [2, 1], [1, -2], [2, -1], [-1, 2], [-2, 1], [-1, -2], [-2, -1]]
    q = deque()
    q.append(start)
    while q:
        x, y = q.popleft()

        if [x, y] == destination:
            print(visited[x][y])
            break
            
        for m in d_lst:
            nx = x + m[0]
            ny = y + m[1]
            if 0 <= nx <len and 0 <= ny < len and visited[nx][ny] == 0:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1


if __name__ == '__main__':

    N = int(input())
    for i in range(N):
        len = int(input())
        start = list(map(int, input().split()))
        destination = list(map(int, input().split()))
        visited = [[0 for i in range(len)] for i in range(len)]
        bfs(start, destination)