QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#743399 | #3128. Rush Hour Puzzle | vwxyz# | TL | 431ms | 18332kb | Python3 | 1.7kb | 2024-11-13 19:07:31 | 2024-11-13 19:07:34 |
Judging History
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)
详细
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