結果
問題 | No.20 砂漠のオアシス |
ユーザー | zimpha |
提出日時 | 2017-12-09 01:55:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 923 ms / 5,000 ms |
コード長 | 985 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 86,988 KB |
実行使用メモリ | 93,248 KB |
最終ジャッジ日時 | 2023-08-20 00:08:45 |
合計ジャッジ時間 | 9,673 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 170 ms
80,628 KB |
testcase_01 | AC | 196 ms
82,408 KB |
testcase_02 | AC | 179 ms
82,372 KB |
testcase_03 | AC | 232 ms
82,788 KB |
testcase_04 | AC | 251 ms
84,264 KB |
testcase_05 | AC | 923 ms
93,248 KB |
testcase_06 | AC | 792 ms
91,828 KB |
testcase_07 | AC | 834 ms
92,324 KB |
testcase_08 | AC | 701 ms
91,256 KB |
testcase_09 | AC | 683 ms
91,024 KB |
testcase_10 | AC | 170 ms
80,680 KB |
testcase_11 | AC | 169 ms
80,684 KB |
testcase_12 | AC | 248 ms
83,816 KB |
testcase_13 | AC | 245 ms
83,276 KB |
testcase_14 | AC | 244 ms
83,384 KB |
testcase_15 | AC | 259 ms
84,452 KB |
testcase_16 | AC | 287 ms
84,760 KB |
testcase_17 | AC | 278 ms
84,632 KB |
testcase_18 | AC | 280 ms
84,300 KB |
testcase_19 | AC | 295 ms
84,740 KB |
testcase_20 | AC | 214 ms
83,292 KB |
ソースコード
from queue import Queue n, v, oy, ox = list(map(int, input().split())) a = [list(map(int, input().split())) for i in range(n)] def get_dist(sx, sy): if sx < 0: return None q = Queue() q.put((sx, sy)) dist = [[1e9] * n for i in range(n)] mark = [[0] * n for i in range(n)] dist[sx][sy] = 0 mark[sx][sy] = 1 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] while not q.empty(): x, y = q.get() mark[x][y] = 0 for i in range(4): xx, yy = x + dx[i], y + dy[i] if xx < 0 or xx >= n or yy < 0 or yy >= n: continue cost = dist[x][y] + a[xx][yy] if dist[xx][yy] > cost: dist[xx][yy] = cost if not mark[xx][yy]: mark[xx][yy] = 1 q.put((xx, yy)) return dist oy -= 1 ox -= 1 d1 = get_dist(0, 0) d2 = get_dist(ox, oy) if d1[n - 1][n - 1] < v: print("YES") elif d2 and d1[ox][oy] < v: v = (v - d1[ox][oy]) * 2 if d2[n - 1][n - 1] < v: print("YES") else: print("NO") else: print("NO")