BOJ 7562:夜の移動

9026 ワード
テキストリンク

ソース:https://www.acmicpc.net/problem/7562


質問する


チェス盤に小夜が置いてある.ナイトが一度に移動できる格子を下図に示します.ナイトが移動したい格子をあげました.ナイトは何回移動すればこの格子に移動できますか?

入力


入力した最初の行は、テスト例の個数を与えます.
各テストボックスは3行で構成されています.1行目はチェス盤の1辺長l(4≦l≦300)を与える.チェス盤の大きさはlです× lです.チェス盤の各コマには2対{0,...,l-1}がある× {0,...,l−1}と表すことができる.2行目と3行目には、nightが現在存在するセル、nightが移動するセルが表示されます.

しゅつりょく


各テストボックスは、最低数回の移動を出力します.

アイデア


DequeによるDFSの実装

コード#コード#


Clone

import sys
from collections import deque
input = lambda :sys.stdin.readline()

dx = (2, 1, -1, -2, -2, -1, 1, 2)
dy = (1, 2, 2, 1, -1, -2, -2, -1)

def bfs():
    q = deque()
    q.append((start_x, start_y))
    while q:
        x, y = q.popleft()
        if x == dst_x and y == dst_y:
            print(d[x][y])
            return
        for i in range(8):
            next_x, next_y = x+dx[i], y+dy[i]
            if next_x < 0 or next_x >= n or next_y < 0 or next_y >= n:
                continue
            if not d[next_x][next_y]:
                d[next_x][next_y] = d[x][y] + 1
                q.append((next_x, next_y))


for _ in range(int(input())):
    n = int(input())
    start_x, start_y = map(int, input().split())
    dst_x, dst_y = map(int, input().split())
    d = [[0]*n for _ in range(n)]
    bfs()

ソース:https://rebas.kr/740

[プログラマー]コードテスト練習-図5級部屋の数
ireportでレポートを作った経験