結果

問題 No.20 砂漠のオアシス
ユーザー nebukuro09nebukuro09
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0