結果

問題 No.2238 Rock and Hole
コンテスト
ユーザー NP
提出日時 2023-04-07 21:07:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,884 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-10-02 18:48:56
合計ジャッジ時間 2,425 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

H, W = map(int, input().split())

# マス目を2次元リストで表現
field = [list(input()) for _ in range(H)]

# 石の位置と穴の位置を取得
stones = []
holes = []
for i in range(H):
    for j in range(W):
        if field[i][j] == "o":
            stones.append((i, j))
            field[i][j] = "." # 石をなくす
        elif field[i][j] == "x":
            holes.append((i, j))

# 石を押す方向を定義
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
dirs = ["L", "R", "U", "D"]

# 石を押す方向を全列挙する再帰関数
def search(stone_idx, path):
    if stone_idx == len(stones): # 全ての石を押した場合
        return True
    si, sj = stones[stone_idx]
    for k in range(4): # 4方向を試す
        ni, nj = si + dy[k], sj + dx[k]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue # マス目外ならスキップ
        if field[ni][nj] == "#":
            continue # 壁ならスキップ
        if (ni, nj) in stones:
            continue # 他の石があればスキップ
        if (ni, nj) in holes: # 穴に入る場合
            field[ni][nj] = "o" # 石を置く
            field[si][sj] = "." # 石をなくす
            if search(stone_idx+1, path + dirs[k]): # 次の石を探す
                return True
            field[ni][nj] = "." # 穴に入らなかった場合
            field[si][sj] = "o" # 石を戻す
        else: # 穴以外の場合
            field[ni][nj] = "o" # 石を置く
            field[si][sj] = "." # 石をなくす
            if search(stone_idx, path + dirs[k]): # 同じ石を押し続ける
                return True
            field[ni][nj] = "." # 石を戻す
            field[si][sj] = "o" # 石を戻す
    return False

# 石を押す方向を全列挙する再帰関数を呼び出す
if search(0, ""):
    print("Yes")
else:
    print("No")
0