結果

問題 No.2213 Neq Move
ユーザー 👑 rin204rin204
提出日時 2023-02-13 18:02:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 320 ms / 2,000 ms
コード長 1,755 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 87,208 KB
実行使用メモリ 80,660 KB
最終ジャッジ日時 2023-09-23 11:52:17
合計ジャッジ時間 3,060 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
71,132 KB
testcase_01 AC 320 ms
80,452 KB
testcase_02 AC 296 ms
79,604 KB
testcase_03 AC 288 ms
79,632 KB
testcase_04 AC 288 ms
80,660 KB
testcase_05 AC 278 ms
79,572 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import *

def solve(a, b, c, d):
    X = sorted({0, 1, 2, a, c})
    Y = sorted({0, 1, 2, b, d})
    mp = {}
    t = 0
    for x in X:
        for y in Y:
            if x == y:
                continue
            mp[(x, y)] = t
            t += 1
    
    edges = [[] for _ in range(t)]
    for x1 in X:
        for x2 in X:
            if x1 == x2:
                continue
            for y in Y:
                if y in [x1, x2]:
                    continue
                if x2 == 0:
                    edges[mp[(x1, y)]].append((mp[(x2, y)], 1))
                elif x1 < y and y < x2:
                    continue
                elif x1 > x2:
                    continue
                else:
                    edges[mp[(x1, y)]].append((mp[(x2, y)], x2 - x1))
                    
    X, Y = Y, X
    for x1 in X:
        for x2 in X:
            if x1 == x2:
                continue
            for y in Y:
                if y in [x1, x2]:
                    continue
                if x2 == 0:
                    edges[mp[(y, x1)]].append((mp[(y, x2)], 1))
                elif x1 < y and y < x2:
                    continue
                elif x1 > x2:
                    continue
                else:
                    edges[mp[(y, x1)]].append((mp[(y, x2)], x2 - x1))

    dist = [1 << 60] * t
    dist[mp[(a, b)]] = 0
    hq = [(0, mp[(a, b)])]
    while hq:
        dd, pos = heappop(hq)
        if dist[pos] < dd:
            continue
        for npos, cc in edges[pos]:
            if dist[npos] > dd + cc:
                dist[npos] = dd + cc
                heappush(hq, (dd + cc, npos))

    return dist[mp[(c, d)]]

for i in range(int(input())):
    ans = solve(*map(int, input().split()))
    print(ans)
0