https://www.acmicpc.net/problem/7562
시간 1초, 메모리 256MB
input :
- 테스트 케이스의 개수
- 한 변의 길이 l(4 ≤ l ≤ 300)
- 나이트가 현재 있는 칸,
- 나이트가 이동하려고 하는 칸
output :
- 나이트가 최소 몇 번만에 이동할 수 있는지 출력
나이트가 이동을 하는 모든 경우의 수 8가지를 만들어 주고 bfs를 수행하자.
좋은 예제 덕분에 시작하는 위치와 도착지가 같은 경우를 예외처리 해야 함을 보여 준다.
예외처리에 주의하고, 빠져나오는 경우에도 bfs를 끝내야 하기 때문에 flag를 마지막에 판별하도록 만들어두자.
import sys
from _collections import deque
t = int(sys.stdin.readline())
for j in range(t):
i = int(sys.stdin.readline())
graph = [[0] * i for k in range(i)]
start_x, start_y = map(int, sys.stdin.readline().split())
target_x, target_y = map(int, sys.stdin.readline().split())
dx = [2, 2, 1, 1, -1, -1, -2, -2]
dy = [1, -1, 2, -2, 2, -2, 1, -1]
q = deque([(start_x, start_y, 0)])
graph[start_x][start_y] = 1
flag = 0
ans = 0
if start_x == target_x and start_y == target_y:
flag = 1
if not flag:
while q:
now_x, now_y, cnt = q.popleft()
for k in range(len(dx)):
nx = now_x + dx[k]
ny = now_y + dy[k]
if nx >= i or ny >= i or nx < 0 or ny < 0:
continue
if nx == target_x and ny == target_y:
ans = cnt + 1
flag = 1
break
if graph[nx][ny] == 0:
graph[nx][ny] = 1
q.append((nx, ny, cnt + 1))
if flag:
break
print(ans)
