CSES - Datatähti 2022 loppu - Results
Submission details
Task:Sokkelo
Sender:okkokko
Submission time:2022-01-22 19:55:46 +0200
Language:Python3 (PyPy3)
Status:READY
Result:28
Feedback
groupverdictscore
#1ACCEPTED28
#20
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2details
#2ACCEPTED0.07 s1, 2details
#3ACCEPTED0.08 s1, 2details
#4ACCEPTED0.59 s2details
#5--2details
#6--2details
#7ACCEPTED0.07 s1, 2details
#8--2details
#9--2details
#10ACCEPTED0.04 s1, 2details
#11ACCEPTED0.52 s2details
#12ACCEPTED0.04 s1, 2details
#13ACCEPTED0.28 s2details
#14ACCEPTED0.04 s1, 2details
#15ACCEPTED0.31 s2details
#16ACCEPTED0.06 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")
sokkelo = [[1 if i == "#" else 0 for i in s] for s in sokStr]
# wall is 1, A is 2, B is 3
def isA(x, y):
if 0 <= x < m and 0 <= y < n:
return sokkelo[y][x] == 2
return False
mi = n + m # ensimmäinen arvo on suurin mahdollinen (manhattan-etäisyys vastakkaisten kulmien välillä)
def Diamond(x, y, d):
"generates all coordinates whose manhattan distance to (x,y) is d"
for i in range(d):
yield (x + d - i, y + i)
yield (x - d + i, y - i)
yield (x + i, y - d + i)
yield (x - i, y + d - i)
def ClosestA(x, y, g):
for d in (range(g - 1, g + 2) if g is not None else range(mi)):
# käy läpi g-1,g,g+1
if any(isA(ix, iy) for ix, iy in Diamond(x, y, d)):
return d
def updateMin(x, y, g):
# g on lähin etäisyys A:n polkuun jonka viereinen kohta sai. Oma lähin etäisyys pitäisi poiketa tästä vain yhdellä
nonlocal mi
e = ClosestA(x, y, g)
if e < mi:
mi = e
return e
def markA(x, y):
if not sokkelo[y][x]:
sokkelo[y][x] = 2
for a in (1, -1):
if 1 <= x + a < m - 1: # jokainen reunaruutu on seinää
# markA(x + a, y)
buffer_markA.append((x + a, y))
if 1 <= y + a < n - 1:
# markA(x, y + a)
buffer_markA.append((x, y + a))
def markB(x, y, g=None):
# g on lähin etäisyys A:n polkuun jonka edellinen kohta sai. Oma lähin etäisyys pitäisi poiketa tästä vain yhdellä
if not sokkelo[y][x]:
sokkelo[y][x] = 3
e = updateMin(x, y, g)
for a in (1, -1):
if 1 <= x + a < m - 1: # jokainen reunaruutu on seinää
buffer_markB.append((x + a, y, e))
if 1 <= y + a < n - 1:
buffer_markB.append((x, y + a, e))
# markA(Ax, Ay) # Virhe on täällä, virhe on RecursionError
buffer_markA = []
buffer_markA.append((Ax, Ay))
while buffer_markA:
markA(*buffer_markA.pop())
if sokkelo[By][Bx] == 2:
print(1)
return
# markB(Bx, By)
buffer_markB = []
buffer_markB.append((Bx, By))
while buffer_markB:
markB(*buffer_markB.pop())
print(mi)
return
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: ACCEPTED

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

correct output
1

user output
1

Test 5

Group: 2

Verdict:

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

correct output
2

user output
(empty)

Test 6

Group: 2

Verdict:

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

correct output
335

user output
(empty)

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
(empty)

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: ACCEPTED

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

correct output
2

user output
2

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