結果
問題 | No.20 砂漠のオアシス |
ユーザー | nebukuro09 |
提出日時 | 2016-09-21 13:30:34 |
言語 | PyPy2 (7.3.13) |
結果 |
AC
|
実行時間 | 514 ms / 5,000 ms |
コード長 | 2,220 bytes |
コンパイル時間 | 587 ms |
コンパイル使用メモリ | 77,544 KB |
実行使用メモリ | 105,656 KB |
最終ジャッジ日時 | 2023-08-03 08:02:53 |
合計ジャッジ時間 | 6,810 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 77 ms
78,104 KB |
testcase_01 | AC | 86 ms
78,608 KB |
testcase_02 | AC | 81 ms
78,316 KB |
testcase_03 | AC | 192 ms
81,880 KB |
testcase_04 | AC | 210 ms
82,672 KB |
testcase_05 | AC | 482 ms
104,296 KB |
testcase_06 | AC | 464 ms
98,944 KB |
testcase_07 | AC | 452 ms
105,600 KB |
testcase_08 | AC | 514 ms
104,976 KB |
testcase_09 | AC | 464 ms
105,656 KB |
testcase_10 | AC | 80 ms
77,860 KB |
testcase_11 | AC | 79 ms
78,132 KB |
testcase_12 | AC | 187 ms
82,836 KB |
testcase_13 | AC | 194 ms
82,732 KB |
testcase_14 | AC | 235 ms
83,212 KB |
testcase_15 | AC | 214 ms
83,152 KB |
testcase_16 | AC | 279 ms
86,668 KB |
testcase_17 | AC | 233 ms
84,540 KB |
testcase_18 | AC | 255 ms
84,616 KB |
testcase_19 | AC | 257 ms
85,040 KB |
testcase_20 | AC | 156 ms
81,008 KB |
ソースコード
import heapq def manhattan(node, goal): return 0 def astar(n, graph, start, goal): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] openlist = [] in_open = set() in_closed = set() f = {(i, j):float('inf') for i in xrange(n) for j in xrange(n)} f[start] = manhattan(start, goal) heapq.heappush(openlist, (f[start], start)) in_open.add(start) while len(openlist) != 0: fval, node = heapq.heappop(openlist) if node not in in_open: continue elif fval != f[node]: continue if node == goal: return f[node] in_open.remove(node) in_closed.add(node) for next_node in [(node[0]+dx[i], node[1]+dy[i]) for i in xrange(4)]: if next_node[0] < 0 or next_node[0] >= n or next_node[1] < 0 or next_node[1] >= n: continue gn = fval - manhattan(node, goal) fdm = gn + graph[next_node[0]][next_node[1]] + manhattan(next_node, goal) if next_node not in in_open and next_node not in in_closed: f[next_node] = fdm heapq.heappush(openlist, (fdm, next_node)) in_open.add(next_node) elif next_node in in_open: if fdm < f[next_node]: f[next_node] = fdm heapq.heappush(openlist, (fdm, next_node)) elif next_node in in_closed: if fdm < f[next_node]: f[next_node] = fdm heapq.heappush(openlist, (fdm, next_node)) in_open.add(next_node) in_closed.remove(next_node) return -1 def parse(): N, V, Ox, Oy = map(int, raw_input().split()) graph = [map(int, raw_input().split()) for _ in xrange(N)] return N, V, graph, (Oy-1, Ox-1) def run(): n, v, graph, oasis = parse() c1 = astar(n, graph, (0, 0), (n-1, n-1)) if oasis == (-1, -1): print 'YES' if c1 < v else 'NO' return c2 = astar(n, graph, (0, 0), oasis) c3 = astar(n, graph, oasis, (n-1, n-1)) #print c1, c2, c3 print 'YES' if c1 < v or (c2 < v and c3 < (v-c2)*2) else 'NO' if __name__ == '__main__': run()