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

問題

アプローチ法

幅優先探索（BFS）を使用して、グリッドAからグリッドBへの最短変換経路を見つける。
各状態（グリッド配置）をノードとし、隣接する行や列の交換をエッジとして考える。
BFSを使用することで、最小の操作回数を求める。

解法手順

1. 入力からグリッドAとBを読み取る。

2. グリッドの状態を効率的に比較・保存するために、各グリッドを不変のタプルに変換する関数を定義する。

3. 幅優先探索のためのキューを初期化し、初期状態（グリッドA）をキューに追加する。

4. 訪問済みの状態と、その状態に到達するまでの操作回数を記録する辞書を初期化する。

5. BFSを開始する：
   a. キューから状態を取り出する。
   b. 現在の状態に対して、可能なすべての行の交換を試みる。
   c. 現在の状態に対して、可能なすべての列の交換を試みる。
   d. 新しい状態が生成されるたびに、それが未訪問であればキューに追加し、操作回数を記録する。

6. BFSの過程で目標状態（グリッドB）に到達した場合、その時点での操作回数が最小の操作回数となる。

7. BFSが終了しても目標状態に到達しなかった場合、変換は不可能であると判断する。

8. 結果を出力する：

   • 変換が可能な場合、最小の操作回数を出力する。
   • 変換が不可能な場合、-1を出力する。

ACコード

ac.py

from collections import deque

# 1. 入力からグリッドAとBを読み取る
def read_grid(N):
    return [list(map(int, input().split())) for _ in range(N)]

# 2. グリッドを不変のタプルに変換する関数
def grid_to_tuple(grid):
    return tuple(tuple(row) for row in grid)

# 3. & 4. BFSの初期化
def initialize_bfs(start_grid):
    queue = deque([(start_grid, 0)])  # (グリッド, 操作回数)のタプルをキューに追加
    visited = {grid_to_tuple(start_grid): 0}  # 訪問済みの状態と操作回数を記録
    return queue, visited

# 5. BFSの実行
def bfs(start_grid, target_grid, H, W):
    queue, visited = initialize_bfs(start_grid)
    target_tuple = grid_to_tuple(target_grid)

    while queue:
        current_grid, steps = queue.popleft()

        # 目標状態に到達したかチェック
        if grid_to_tuple(current_grid) == target_tuple:
            return steps

        # 行の交換を試みる
        for i in range(H-1):
            new_grid = [row[:] for row in current_grid]
            new_grid[i], new_grid[i+1] = new_grid[i+1], new_grid[i]
            new_tuple = grid_to_tuple(new_grid)
            if new_tuple not in visited:
                queue.append((new_grid, steps + 1))
                visited[new_tuple] = steps + 1

        # 列の交換を試みる
        for j in range(W-1):
            new_grid = [row[:] for row in current_grid]
            for i in range(H):
                new_grid[i][j], new_grid[i][j+1] = new_grid[i][j+1], new_grid[i][j]
            new_tuple = grid_to_tuple(new_grid)
            if new_tuple not in visited:
                queue.append((new_grid, steps + 1))
                visited[new_tuple] = steps + 1

    # 目標状態に到達できなかった場合
    return -1

# メイン処理
def solve():
    # グリッドAとBを読み取る
    H, W = map(int, input().split())
    grid_a = read_grid(H)
    grid_b = read_grid(H)

    # BFSを実行して最小操作回数を求める
    result = bfs(grid_a, grid_b, H, W)

    # 結果を出力
    print(result)

# プログラムの実行
if __name__ == "__main__":
    solve()