結果
問題 |
No.2708 Jewel holder
|
ユーザー |
|
提出日時 | 2024-11-01 20:31:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,181 bytes |
コンパイル時間 | 543 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 76,824 KB |
最終ジャッジ日時 | 2024-11-01 20:31:51 |
合計ジャッジ時間 | 2,509 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 WA * 8 |
ソースコード
H, W = map(int, input().split()) A = [input() for _ in range(H)] # 壁は"#" # 通路は"." # 2方向移動 dx = [1, 0] dy = [0, 1] # 壁を追加 A = ["#" * (W + 2)] + ["#" + a + "#" for a in A] + ["#" * (W + 2)] # スタートは(1, 1) sx, sy = 1, 1 # ゴールは(H, W) gx, gy = H, W # 宝石がもらえるマス jewel = "o" # 宝石が奪われるマス trap = "x" ans = 0 # スタートからゴールの内、最短距離の経路の内、宝石が一つ以上ある経路の数を求める # 再帰関数 def dfs(x, y, cnt): # 宝石がある場合 if A[x][y] == jewel: cnt += 1 # 宝石が奪われる場合 if A[x][y] == trap: cnt -= 1 if cnt < 0: return # ゴールに到達した場合 if x == gx and y == gy: if A[x][y] == jewel: cnt += 1 if A[x][y] == trap: cnt -= 1 if cnt >= 1: global ans ans += 1 # 4方向に進む for i in range(2): nx = x + dx[i] ny = y + dy[i] # 進める場合 if A[nx][ny] != "#": # 移動 dfs(nx, ny, cnt) dfs(sx, sy, 0) print(ans)