QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743399#3128. Rush Hour Puzzlevwxyz#TL 431ms18332kbPython31.7kb2024-11-13 19:07:312024-11-13 19:07:34

Judging History

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

  • [2024-11-13 19:07:34]
  • 评测
  • 测评结果:TL
  • 用时:431ms
  • 内存:18332kb
  • [2024-11-13 19:07:31]
  • 提交

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):
                B[i][j]=0
            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):
                B[i][j]=0
            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: 81ms
memory: 11972kb

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: 0
Accepted
time: 16ms
memory: 10888kb

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:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 38ms
memory: 11188kb

input:

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

output:

8

result:

ok single line: '8'

Test #4:

score: 0
Accepted
time: 431ms
memory: 18332kb

input:

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

output:

8

result:

ok single line: '8'

Test #5:

score: 0
Accepted
time: 80ms
memory: 11724kb

input:

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

output:

10

result:

ok single line: '10'

Test #6:

score: 0
Accepted
time: 20ms
memory: 10668kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 48ms
memory: 11144kb

input:

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

output:

6

result:

ok single line: '6'

Test #8:

score: 0
Accepted
time: 124ms
memory: 12176kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 15ms
memory: 10712kb

input:

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

output:

10

result:

ok single line: '10'

Test #10:

score: -100
Time Limit Exceeded

input:

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

output:


result: