Zenn
⛳

【競技プログラミング】AtCoder Beginner Contest 272_D問題

2024/12/24に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc272/tasks/abc272_d

要約

  1. N×N のマス目がある。
  2. 駒は最初 (1,1) にある。
  3. 駒は現在の位置から距離がちょうど √M のマスに移動できる。
  4. 各マス (i,j) について、(1,1) から (i,j) に移動できるかを判定し、可能な場合は最小の操作回数を求める。

変数情報：

  • N: マス目の大きさ（N×N）
  • M: 移動可能な距離の2乗
  • i, j: 目標のマスの座標 (1 ≤ i, j ≤ N)

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

幅優先探索（BFS）を用いて、(1,1)から各マスへの最短経路を求める。
マス目全体をグラフとみなし、距離√Mで移動可能なマス同士をエッジで結ぶ。
BFSを使用することで、各マスへの最小操作回数を効率的に計算できる。

解法手順

  1. 入力値N（マス目の大きさ）とM（移動可能な距離の2乗）を受け取る。
  2. 移動可能な方向のセットDを作成する。
  3. 距離を記録する2次元配列distを初期化し、全てのマスを-1（未訪問）で埋める。
  4. (1,1)の距離を0に設定し、キューに追加する。
  5. キューが空になるまで以下の処理を繰り返す：
    a. キューから現在のマスの座標を取り出す。
    b. 現在のマスから移動可能な全ての方向について：
    • 新しいマスの座標を計算する。
    • 新しいマスが盤面内かつ未訪問であれば：
      • 新しいマスの距離を設定（現在のマスの距離+1）。
      • 新しいマスをキューに追加する。
  6. 全てのマスについて、計算された距離（到達不可能な場合は-1）を出力する。

ACコード

ac.py

from collections import deque

def io_func():
    # 入力値N（マス目の大きさ）とM（移動可能な距離の2乗）を受け取る
    N, M = map(int, input().split())
    return N, M

def solve(N, M):
    # 移動可能な方向のセットDを作成する
    D = set()
    for di in range(N):
        if di ** 2 > M:
            break
        dj = int((M - di ** 2) ** 0.5)
        if di ** 2 + dj ** 2 == M:
            D.update([(di, dj), (-di, dj), (di, -dj), (-di, -dj)])
    
    # 距離を記録する2次元配列distを初期化し、全てのマスを-1（未訪問）で埋める
    dist = [[-1] * N for _ in range(N)]
    
    # (1,1)の距離を0に設定し、キューに追加する
    dist[0][0] = 0
    q = deque([0])
    
    # キューが空になるまでBFSを実行
    while q:
        # キューから現在のマスの座標を取り出す
        ci, cj = divmod(q.popleft(), N)
        
        # 現在のマスから移動可能な全ての方向について処理
        for di, dj in D:
            ni, nj = ci + di, cj + dj
            
            # 新しいマスが盤面内かつ未訪問であれば処理
            if 0 <= ni < N and 0 <= nj < N and dist[ni][nj] < 0:
                # 新しいマスの距離を設定（現在のマスの距離+1）
                dist[ni][nj] = dist[ci][cj] + 1
                # 新しいマスをキューに追加する
                q.append(ni * N + nj)
    
    # 全てのマスについて、計算された距離を出力
    for row in dist:
        print(*row)

# メイン処理
N, M = io_func()
solve(N, M)

# ###
# N: マス目の大きさ
# M: 移動可能な距離の2乗
# D: 移動可能な方向のセット
# dist: 各マスへの最短距離を格納する2次元配列
# q: BFSで使用するキュー
# ci, cj: 現在のマスの座標
# ni, nj: 新しいマスの座標
# di, dj: 移動方向

# 1. io_func関数:
#    - 標準入力からNとMを受け取る
# 2. solve関数:
#    a. 移動可能な方向のセットDを作成
#    b. 距離を記録する2次元配列distを初期化
#    c. 始点(1,1)の設定とBFSの準備
#    d. BFSを実行し、各マスへの最短距離を計算
#    e. 結果を出力
# 3. メイン処理:
#    - io_func関数を呼び出してNとMを取得
#    - solve関数を呼び出して問題を解く

Discussion