CSES - Datatähti 2022 loppu - Results
Submission details
Task:Sokkelo
Sender:okkokko
Submission time:2022-01-22 16:49:34 +0200
Language:PyPy3
Status:READY
Result:28
Feedback
groupverdictscore
#1ACCEPTED28
#20
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2details
#2ACCEPTED0.05 s1, 2details
#3ACCEPTED0.05 s1, 2details
#40.24 s2details
#50.22 s2details
#60.23 s2details
#7ACCEPTED0.04 s1, 2details
#80.23 s2details
#9--2details
#10ACCEPTED0.06 s1, 2details
#110.22 s2details
#12ACCEPTED0.04 s1, 2details
#13ACCEPTED0.14 s2details
#14ACCEPTED0.04 s1, 2details
#15ACCEPTED0.10 s2details
#16ACCEPTED0.05 s2details
#17ACCEPTED0.07 s2details

Code

from itertools import product


def I():
    return map(int, input().split())


def main():
    n, m = I()  # y,x
    sokStr = [input() for _ in range(n)]

    def findPerson(person):
        for i in range(n):
            a = sokStr[i].find(person)
            if a != -1:
                return a, i
    Ax, Ay = findPerson("A")
    Bx, By = findPerson("B")
    Apath = []
    Bpath = []
    sokkelo = [[1 if i == "#" else 0 for i in s] for s in sokStr]
    # wall is 1, A is 2, B is 3

    def mark(x, y, side):
        if not sokkelo[y][x]:
            sokkelo[y][x] = side
            (Apath if side == 2 else Bpath).append((y, x))
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    mark(x + a, y, side)
                if 1 <= y + a < n - 1:
                    mark(x, y + a, side)

    def markA(x, y):
        if not sokkelo[y][x]:
            sokkelo[y][x] = 2
            try:
                Apath.append((y, x))
            except:
                pass
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    markA(x + a, y)
                if 1 <= y + a < n - 1:
                    markA(x, y + a)

    def markB(x, y):
        if not sokkelo[y][x]:
            sokkelo[y][x] = 3
            try:
                Bpath.append((y, x))
            except:
                pass
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    markB(x + a, y)
                if 1 <= y + a < n - 1:
                    markB(x, y + a)
    try:
        markA(Ax, Ay)  # Virhe on täällä, ei ole IndexError
    except:
        # print(0)
        # return
        pass
    if sokkelo[By][Bx] == 2:
        print(1)
        return
    try:
        markB(Bx, By)
    except:
        pass

    def manhattan(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
    print(min(manhattan(a, b) for a, b in product(Apath, Bpath)))


if __name__ == "__main__":
    main()

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#A.................#
#..................#
#..................#
...

correct output
1

user output
1

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#A.................#
#..................#
#..................#
...

correct output
2

user output
2

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#A.................#
#..................#
#..................#
...

correct output
9

user output
9

Test 4

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
1

user output
105

Test 5

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
2

user output
499

Test 6

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
335

user output
666

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#####.##############
###.....############
##.......###########
...

correct output
10

user output
10

Test 8

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
436

user output
718

Test 9

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
2

user output
(empty)

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#B................##
#################.##
#################.##
...

correct output
2

user output
2

Test 11

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
2

user output
3

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
##########A#########
##########.#########
##########.#########
...

correct output
2

user output
2

Test 13

Group: 2

Verdict: ACCEPTED

input
1000 1000
##############################...

correct output
2

user output
2

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
##########A#########
##########.#########
##########.#########
...

correct output
12

user output
12

Test 15

Group: 2

Verdict: ACCEPTED

input
1000 1000
##############################...

correct output
502

user output
502

Test 16

Group: 2

Verdict: ACCEPTED

input
3 1000
##############################...

correct output
1

user output
1

Test 17

Group: 2

Verdict: ACCEPTED

input
1000 3
###
#A#
#.#
#.#
...

correct output
1

user output
1