编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#101532 #1437. [L3-2] Ice World Time Limit Exceeded 50 49467 ms 655364 K Python 3 / 5.1 K wyhao 2024-03-13 0:42:00
N = 31
n = 0
a1 = 0
a2 = 0
b1 = 0
b2 = 0
c1 = 0
c2 = 0
d1 = 0
d2 = 0
dp = [[[[[[0 for _ in range(4)] for _ in range(4)] for _ in range(N)] for _ in range(N)] for _ in range(N)] for _ in range(N)]
vis = [[[[[[0 for _ in range(4)] for _ in range(4)] for _ in range(1)] for _ in range(1)] for _ in range(1)] for _ in range(1)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def tt(x1,x2,y1,y2):
    global n
    t1 = x1+y1-2
    t2 = 2*n-x2-y2
    if t1==t2:
        return 1
    else:
        return 0
def cp1(x1,y1,xx,yy):
    global a1,b1,c1,d1
    if x1==a1 and y1==b1 and xx==c1 and yy==d1:
        return True
    if x1==c1 and y1==d1 and xx==a1 and yy==b1:
        return True
    return False
def cp2(x1,y1,xx,yy):
    global a2,b2,c2,d2
    if x1==a2 and y1==b2 and xx==c2 and yy==d2:
        return True
    if x1==c2 and y1==d2 and xx==a2 and yy==b2:
        return True
    return False
def chk(x1,y1,x2,y2,t1,t2):
    d = abs(x1-x2)+abs(y1-y2)
    if d<=1:
        if t1&1:
            return 1
        if t2&1:
            return -1
    if x1==x2 or y1==y2:
        if t1&2:
            return 1
        if t2&2:
            return -1
    return 0

def f(x1,y1,x2,y2,t1,t2):
    global vis,dp,dx,dy
    if vis[x1][y1][x2][y2][t1][t2]:
        return dp[x1][y1][x2][y2][t1][t2]
    # print(x1,y1,x2,y2,t1,t2)
    vis[x1][y1][x2][y2][t1][t2]=True
    global n
    if x1==n and y1==n and x2==1 and y2==1:
        dp[x1][y1][x2][y2][t1][t2]=0
        return 0
    t=tt(x1,y1,x2,y2)
    if t==1:
        ansk=-1
        for k in range(0,2):
            xx=x1+dx[k]
            yy=y1+dy[k]
            if xx<1 or xx>n or yy<1 or yy>n:
                continue
            if ((t2&1)!=1) and cp1(x1,y1,xx,yy):
                d=chk(xx,yy,x2,y2,t1+1,t2)
                if d==1:
                    dp[x1][y1][x2][y2][t1][t2]=1
                    return 1
                elif d==-1:
                    continue
                d=f(xx,yy,x2,y2,t1+1,t2)
                if(d==1):
                    dp[x1][y1][x2][y2][t1][t2]=1
                    return 1
                ansk=max(ansk,d)
            if ((t2&2)!=2) and cp2(x1,y1,xx,yy):
                d=chk(xx,yy,x2,y2,t1+2,t2)
                if d==1:
                    dp[x1][y1][x2][y2][t1][t2]=1
                    return 1
                elif d==-1:
                    continue
                d=f(xx,yy,x2,y2,t1+2,t2)
                if(d==1):
                    dp[x1][y1][x2][y2][t1][t2]=1
                    return 1
                ansk=max(ansk,d)
            d=chk(xx,yy,x2,y2,t1,t2)
            if d==1:
                dp[x1][y1][x2][y2][t1][t2]=1
                return 1
            elif d==-1:
                continue
            d=f(xx,yy,x2,y2,t1,t2)
            if(d==1):
                dp[x1][y1][x2][y2][t1][t2]=1
                return 1
            ansk=max(ansk,d)
        dp[x1][y1][x2][y2][t1][t2]=ansk
        return ansk
    else:
        ansk=1
        for k in range(2,4):
            xx=x2+dx[k]
            yy=y2+dy[k]
            if(xx<1 or xx>n or yy<1 or yy>n):
                continue
            if((t1&1)!=1) and (cp1(x2,y2,xx,yy)):
                d=chk(x1,y1,xx,yy,t1,t2+1)
                if(d==-1):
                    dp[x1][y1][x2][y2][t1][t2]=-1
                    return -1
                elif(d==1):
                    continue
                d=f(x1,y1,xx,yy,t1,t2+1)
                if(d==-1):
                    dp[x1][y1][x2][y2][t1][t2]=-1
                    return -1
                ansk=min(ansk,d)
            if((t1&2)!=2) and (cp2(x2,y2,xx,yy)):
                d=chk(x1,y1,xx,yy,t1,t2+2)
                if(d==-1):
                    dp[x1][y1][x2][y2][t1][t2]=-1
                    return -1
                elif(d==1):
                    continue
                d=f(x1,y1,xx,yy,t1,t2+2)
                if(d==-1):
                    dp[x1][y1][x2][y2][t1][t2]=-1
                    return -1
                ansk=min(ansk,d)
            d=chk(x1,y1,xx,yy,t1,t2)
            if d==-1:
                dp[x1][y1][x2][y2][t1][t2]=-1
                return -1
            elif d==1:
                continue
            d=f(x1,y1,xx,yy,t1,t2)
            if(d==-1):
                dp[x1][y1][x2][y2][t1][t2]=-1
                return -1
            ansk=min(ansk,d)
        dp[x1][y1][x2][y2][t1][t2]=ansk
        return ansk



def main():
    tests = int(input())
    for i in range(tests):
        global n,a1,a2,b1,b2,c1,c2,d1,d2,vis
        str = input().split(" ")
        n=int(str[0])
        a1=int(str[1])
        b1=int(str[2])
        c1=int(str[3])
        d1=int(str[4])
        a2=int(str[5])
        b2=int(str[6])
        c2=int(str[7])
        d2=int(str[8])
        N=n+1
        vis = [[[[[[0 for _ in range(4)] for _ in range(4)] for _ in range(N)] for _ in range(N)] for _ in range(N)] for _ in range(N)]
        d = f(1,1,n,n,0,0)
        if d==1:
            print("Alice")
        elif d==-1:
            print("Bob")
        else:
            print("0")

main()
子任务 #1
Time Limit Exceeded
得分:50
测试点 #1
Accepted
得分:100
用时:4795 ms
内存:454528 KiB

输入文件(1.in

20
2 2 1 2 2 1 1 1 2
2 1 1 2 1 1 1 1 2
2 2 1 2 2 2 1 2 2
2 1 2 2 2 2 1 2 2
2 1 1 1 2 1 1 1 2
2 1 1 2
<262 bytes omitted>

答案文件(1.out

Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alic
<14 bytes omitted>

用户输出

Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:4720 ms
内存:456820 KiB

输入文件(2.in

20
5 5 3 5 4 2 4 3 4
5 2 3 3 3 2 2 2 3
4 2 1 2 2 3 4 4 4
6 1 2 1 3 1 2 2 2
6 5 1 5 2 6 5 6 6
4 4 3 4
<262 bytes omitted>

答案文件(2.out

Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice

用户输出

Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4833 ms
内存:456340 KiB

输入文件(3.in

20
3 1 3 2 3 1 2 1 3
6 6 2 6 3 5 4 5 5
4 4 2 4 3 1 2 2 2
3 1 3 2 3 2 2 3 2
3 2 2 3 2 1 3 2 3
5 4 1 5
<262 bytes omitted>

答案文件(3.out

Alice
Bob
Alice
0
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
0
Alice
Bob
Bob
Alice
Bob

用户输出

Alice
Bob
Alice
0
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
0
Alice
Bob
Bob
Alice
Bob

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:4879 ms
内存:456740 KiB

输入文件(4.in

20
5 4 3 4 4 2 3 2 4
4 3 4 4 4 3 4 4 4
3 2 1 2 2 2 3 3 3
4 1 4 2 4 1 1 1 2
4 1 1 1 2 4 1 4 2
6 3 4 3
<262 bytes omitted>

答案文件(4.out

Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bo
<2 bytes omitted>

用户输出

Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:4895 ms
内存:456352 KiB

输入文件(5.in

20
3 2 2 3 2 1 1 1 2
6 5 5 5 6 1 5 2 5
3 2 3 3 3 2 1 3 1
5 1 3 1 4 2 3 2 4
5 2 3 3 3 2 5 3 5
4 1 2 1
<262 bytes omitted>

答案文件(5.out

Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
0
Alice
Alice
Bob
Alice

用户输出

Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
0
Alice
Alice
Bob
Alice

系统信息

Exited with return code 0
测试点 #6
Time Limit Exceeded
得分:0
用时:5052 ms
内存:468904 KiB

输入文件(6.in

20
9 4 2 4 3 4 7 5 7
9 3 7 4 7 4 4 5 4
10 2 9 3 9 9 8 10 8
9 4 1 5 1 7 7 7 8
9 8 7 9 7 4 1 5 1
10 7 
<276 bytes omitted>

答案文件(6.out

Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
0
0
Alice
Alice
Alice
Bob

用户输出

Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
0
0
Alice
Alice
Alice
Bob
测试点 #7
Time Limit Exceeded
得分:0
用时:5068 ms
内存:468912 KiB

输入文件(7.in

20
10 4 2 5 2 8 1 8 2
9 9 3 9 4 6 3 7 3
10 4 6 5 6 3 4 3 5
9 7 9 8 9 1 6 2 6
9 7 7 7 8 6 8 7 8
9 4 3
<274 bytes omitted>

答案文件(7.out

Alice
Bob
Alice
0
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice

用户输出

Alice
Bob
Alice
0
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
测试点 #8
Time Limit Exceeded
得分:0
用时:5074 ms
内存:617744 KiB

输入文件(8.in

20
12 11 6 11 7 4 7 5 7
10 3 7 4 7 7 1 8 1
18 9 16 10 16 12 10 12 11
22 12 13 13 13 4 9 5 9
5 4 2 4 
<344 bytes omitted>

答案文件(8.out

Alice
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice

用户输出

Alice
Alice
Bob
测试点 #9
Time Limit Exceeded
得分:0
用时:5065 ms
内存:601532 KiB

输入文件(9.in

20
5 3 2 4 2 4 2 4 3
6 5 3 5 4 3 2 4 2
5 4 5 5 5 4 1 5 1
8 5 6 5 7 7 5 7 6
21 3 4 3 5 18 21 19 21
15
<339 bytes omitted>

答案文件(9.out

Alice
0
Bob
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Alice
Alice

用户输出

Alice
0
Bob
Bob
Bob
Alice
Bob
测试点 #10
Time Limit Exceeded
得分:0
用时:5086 ms
内存:655364 KiB

输入文件(10.in

20
30 16 8 16 9 9 24 9 25
30 6 6 7 6 15 23 16 23
30 28 23 28 24 8 12 9 12
30 22 24 23 24 28 28 29 28
<399 bytes omitted>

答案文件(10.out

Bob
Bob
0
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob