Submission #50023464

Source Code Expand

from collections import deque

Vec = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = 1 << 63


def clamp(v, lo, hi):
    if v < lo:
        return lo
    if hi < v:
        return hi
    else:
        return v


def moved_coord(i, j, di, dj):
    nex_i, nex_j = clamp(i + di, 0, N - 1), clamp(j + dj, 0, N - 1)
    if S[nex_i][nex_j] == '#':
        return i, j
    else:
        return nex_i, nex_j


N = int(input())
S = [input() for _ in range(N)]

P = []
for i in range(N):
    for j in range(N):
        if S[i][j] == 'P':
            P.append((i, j))

# dp[i1][j1][i2][j2]: プレイヤー2人の座標が(i1,j1), (i2,j2)になるまでの操作回数の最小値
dp = [[[[-1] * N for _ in range(N)] for _ in range(N)] for _ in range(N)]
(i1, j1), (i2, j2) = P
dp[i1][j1][i2][j2] = 0
dp[i2][j2][i1][j1] = 0
que = deque()
que.append((i1, j1, i2, j2))

while que:
    i1, j1, i2, j2 = que.popleft()
    for di, dj in Vec:
        nex_i1, nex_j1 = moved_coord(i1, j1, di, dj)
        nex_i2, nex_j2 = moved_coord(i2, j2, di, dj)
        if dp[nex_i1][nex_j1][nex_i2][nex_j2] == -1:
            dp[nex_i1][nex_j1][nex_i2][nex_j2] = dp[i1][j1][i2][j2] + 1
            dp[nex_i2][nex_j2][nex_i1][nex_j1] = dp[i1][j1][i2][j2] + 1
            que.append((nex_i1, nex_j1, nex_i2, nex_j2))

ans = INF
for i in range(N):
    for j in range(N):
        if dp[i][j][i][j] != -1:
            ans = min(ans, dp[i][j][i][j])

if ans == INF:
    print(-1)
else:
    print(ans)

Submission Info

Submission Time
Task D - Synchronized Players
User hyouchun
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 1519 Byte
Status TLE
Exec Time 4212 ms
Memory 489580 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 54
TLE × 1
Set Name Test Cases
Sample sample00.txt, sample01.txt, sample02.txt
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt, testcase42.txt, testcase43.txt, testcase44.txt, testcase45.txt, testcase46.txt, testcase47.txt, testcase48.txt, testcase49.txt, testcase50.txt, testcase51.txt
Case Name Status Exec Time Memory
sample00.txt AC 74 ms 81124 KiB
sample01.txt AC 69 ms 76732 KiB
sample02.txt AC 78 ms 82188 KiB
testcase00.txt AC 615 ms 211840 KiB
testcase01.txt AC 473 ms 207196 KiB
testcase02.txt AC 613 ms 211272 KiB
testcase03.txt AC 359 ms 201612 KiB
testcase04.txt AC 584 ms 210452 KiB
testcase05.txt AC 963 ms 193796 KiB
testcase06.txt AC 1390 ms 251996 KiB
testcase07.txt AC 945 ms 194760 KiB
testcase08.txt AC 1332 ms 247744 KiB
testcase09.txt AC 946 ms 192000 KiB
testcase10.txt AC 1427 ms 256772 KiB
testcase11.txt AC 1078 ms 215464 KiB
testcase12.txt AC 1357 ms 254620 KiB
testcase13.txt AC 1381 ms 254768 KiB
testcase14.txt AC 1360 ms 251768 KiB
testcase15.txt AC 563 ms 202164 KiB
testcase16.txt AC 656 ms 224552 KiB
testcase17.txt AC 259 ms 197700 KiB
testcase18.txt AC 267 ms 207512 KiB
testcase19.txt AC 211 ms 206664 KiB
testcase20.txt AC 269 ms 207448 KiB
testcase21.txt AC 234 ms 206712 KiB
testcase22.txt AC 1245 ms 229644 KiB
testcase23.txt AC 839 ms 235772 KiB
testcase24.txt AC 2442 ms 365588 KiB
testcase25.txt AC 3999 ms 489580 KiB
testcase26.txt AC 3704 ms 448848 KiB
testcase27.txt TLE 4212 ms 466920 KiB
testcase28.txt AC 3215 ms 446116 KiB
testcase29.txt AC 3897 ms 480060 KiB
testcase30.txt AC 2357 ms 363780 KiB
testcase31.txt AC 3752 ms 460368 KiB
testcase32.txt AC 3408 ms 441680 KiB
testcase33.txt AC 3468 ms 448764 KiB
testcase34.txt AC 2301 ms 356408 KiB
testcase35.txt AC 3315 ms 420756 KiB
testcase36.txt AC 2677 ms 371876 KiB
testcase37.txt AC 3155 ms 430136 KiB
testcase38.txt AC 2310 ms 348108 KiB
testcase39.txt AC 2984 ms 362528 KiB
testcase40.txt AC 2465 ms 353864 KiB
testcase41.txt AC 2869 ms 371284 KiB
testcase42.txt AC 2061 ms 334116 KiB
testcase43.txt AC 2601 ms 361252 KiB
testcase44.txt AC 1816 ms 320936 KiB
testcase45.txt AC 2549 ms 362880 KiB
testcase46.txt AC 2230 ms 348020 KiB
testcase47.txt AC 2284 ms 347252 KiB
testcase48.txt AC 1458 ms 263288 KiB
testcase49.txt AC 2283 ms 349596 KiB
testcase50.txt AC 1359 ms 246116 KiB
testcase51.txt AC 2195 ms 339872 KiB