結果

問題 No.2238 Rock and Hole
ユーザー NPNP
提出日時 2023-04-07 21:07:47
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,884 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-10-02 18:48:56
合計ジャッジ時間 2,425 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
10,880 KB
testcase_01 WA -
testcase_02 AC 32 ms
10,752 KB
testcase_03 WA -
testcase_04 AC 32 ms
10,624 KB
testcase_05 WA -
testcase_06 AC 30 ms
10,752 KB
testcase_07 AC 31 ms
10,880 KB
testcase_08 AC 31 ms
10,752 KB
testcase_09 AC 31 ms
10,752 KB
testcase_10 AC 62 ms
11,520 KB
testcase_11 AC 56 ms
11,520 KB
testcase_12 AC 51 ms
11,136 KB
testcase_13 AC 52 ms
11,136 KB
testcase_14 AC 41 ms
11,008 KB
testcase_15 AC 69 ms
11,776 KB
testcase_16 AC 54 ms
11,520 KB
testcase_17 AC 55 ms
11,392 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 51 ms
11,136 KB
testcase_21 WA -
testcase_22 AC 49 ms
11,392 KB
testcase_23 AC 31 ms
10,880 KB
権限があれば一括ダウンロードができます

ソースコード

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