結果

問題 No.2708 Jewel holder
ユーザー FromBooskaFromBooska
提出日時 2024-03-31 16:52:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,226 ms / 2,000 ms
コード長 1,489 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 83,920 KB
最終ジャッジ日時 2024-03-31 16:52:56
合計ジャッジ時間 3,667 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,460 KB
testcase_01 AC 39 ms
53,460 KB
testcase_02 AC 38 ms
53,460 KB
testcase_03 AC 38 ms
53,460 KB
testcase_04 AC 38 ms
53,460 KB
testcase_05 AC 39 ms
53,460 KB
testcase_06 AC 37 ms
53,460 KB
testcase_07 AC 39 ms
53,460 KB
testcase_08 AC 37 ms
53,460 KB
testcase_09 AC 38 ms
53,460 KB
testcase_10 AC 38 ms
53,460 KB
testcase_11 AC 92 ms
75,716 KB
testcase_12 AC 38 ms
53,460 KB
testcase_13 AC 61 ms
67,952 KB
testcase_14 AC 43 ms
59,576 KB
testcase_15 AC 1,226 ms
83,920 KB
testcase_16 AC 54 ms
65,920 KB
testcase_17 AC 455 ms
79,844 KB
testcase_18 AC 102 ms
76,116 KB
testcase_19 AC 113 ms
76,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 盤面が非常に小さい、visited管理してDFSにしよう
# 問題文では「没収されるときに1つも宝石を持っていない状況」とあるが0個になるのはOKなのか
# 動きが上下左右だけというのも書いてない

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append(input())
    
import sys
sys.setrecursionlimit(10**7)

def dfs(ch, cw, step, coin):
    global ans_list, min_step    
    
    #print('ch', ch, 'cw', cw, 'step', step, 'coin', coin)
    #print('visited', visited)
    #print()
    if step > min_step:
        return

    if (ch, cw)==(H-1, W-1):
        ans_list.append(step)
        if step < min_step:
            min_step = step
        return
    
    for dh, dw in d:
        if 0 <= ch+dh < H and 0 <= cw+dw < W and visited[ch+dh][cw+dw ]==0:
            if A[ch+dh][cw+dw] == 'o':
                visited[ch+dh][cw+dw ]=1
                dfs(ch+dh, cw+dw, step+1, coin+1)
                visited[ch+dh][cw+dw ]=0
            elif A[ch+dh][cw+dw] == 'x':
                if coin>=1:
                    visited[ch+dh][cw+dw ]=1
                    dfs(ch+dh, cw+dw, step+1, coin-1)
                    visited[ch+dh][cw+dw ]=0
    
d = [[+1, 0], [-1, 0], [0, +1], [0, -1]]
min_step = 10**3
ans_list = []
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
dfs(0, 0, 0, 1)
#print(ans_list)

if len(ans_list)>0:
    min_step = min(ans_list)
    ans = ans_list.count(min_step)
else:
    ans = 0
print(ans)
0