QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743379#3128. Rush Hour Puzzlevwxyz#WA 28ms10760kbPython31.6kb2024-11-13 19:04:542024-11-13 19:04:55

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 19:04:55]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:10760kb
  • [2024-11-13 19:04:54]
  • 提交

answer

from functools import lru_cache
N=6
A=tuple(tuple(map(int,input().split())) for i in range(N))
M=max(A[i][j] for i in range(N) for j in range(N))
def move(A,a):
    retu=[[A[i][j] for j in range(N)] for i in range(N)]
    I=[]
    J=[]
    for i in range(N):
        for j in range(N):
            if A[i][j]==a:
                I.append(i)
                J.append(j)
    retu=[]
    if J[0]==J[-1]:
        for di in (-1,1):
            B=[[A[i][j] for j in range(N)] for i in range(N)]
            dj=0
            ok=True
            for i,j in zip(I,J):
                if 0<=i+di<N and 0<=j+dj<N and A[i+di][j+dj] in (0,a):
                    B[i+di][j+dj]=A[i][j]
                else:
                    ok=False
            if ok:
                retu.append(B)
    else:
        for dj in (-1,1):
            B=[[A[i][j] for j in range(N)] for i in range(N)]
            di=0
            ok=True
            for i,j in zip(I,J):
                if 0<=i+di<N and 0<=j+dj<N and A[i+di][j+dj] in (0,a):
                    B[i+di][j+dj]=A[i][j]
                else:
                    ok=False
            if ok:
                retu.append(B)
    return retu
            


@lru_cache(maxsize=None)
def solve(A,cnt):
    if cnt<=1:
        return -1
    if A[2][5]==1 and A[2][4]==1:
        return cnt-2
    retu=-1
    for a in range(1,M+1):
        for B in move(A,a):
            for i in range(N):
                B[i]=tuple(B[i])
            B=tuple(B)
            retu=max(retu,solve(B,cnt-1))
    return retu



ans=solve(A,10)
if ans!=-1:
    ans=10-ans
print(ans)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 28ms
memory: 10760kb

input:

2 2 0 0 0 7
3 0 0 5 0 7
3 1 1 5 0 7
3 0 0 5 0 0
4 0 0 0 8 8
4 0 6 6 6 0

output:

-1

result:

ok single line: '-1'

Test #2:

score: -100
Wrong Answer
time: 12ms
memory: 10716kb

input:

0 2 0 6 6 0
0 2 0 0 7 0
0 3 1 1 7 0
0 3 4 4 8 0
0 5 5 5 8 0
0 0 0 0 0 0

output:

-1

result:

wrong answer 1st lines differ - expected: '6', found: '-1'