Task: | Sokkelo |
Sender: | okkokko |
Submission time: | 2022-01-22 19:55:46 +0200 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | 28 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 28 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.04 s | 1, 2 | details |
#2 | ACCEPTED | 0.07 s | 1, 2 | details |
#3 | ACCEPTED | 0.08 s | 1, 2 | details |
#4 | ACCEPTED | 0.59 s | 2 | details |
#5 | TIME LIMIT EXCEEDED | -- | 2 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | ACCEPTED | 0.07 s | 1, 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | ACCEPTED | 0.04 s | 1, 2 | details |
#11 | ACCEPTED | 0.52 s | 2 | details |
#12 | ACCEPTED | 0.04 s | 1, 2 | details |
#13 | ACCEPTED | 0.28 s | 2 | details |
#14 | ACCEPTED | 0.04 s | 1, 2 | details |
#15 | ACCEPTED | 0.31 s | 2 | details |
#16 | ACCEPTED | 0.06 s | 2 | details |
#17 | ACCEPTED | 0.07 s | 2 | details |
Code
from itertools import productdef I():return map(int, input().split())def main():n, m = I() # y,xsokStr = [input() for _ in range(n)]def findPerson(person):for i in range(n):a = sokStr[i].find(person)if a != -1:return a, iAx, 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 3def isA(x, y):if 0 <= x < m and 0 <= y < n:return sokkelo[y][x] == 2return Falsemi = 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+1if any(isA(ix, iy) for ix, iy in Diamond(x, y, d)):return ddef 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 mie = ClosestA(x, y, g)if e < mi:mi = ereturn edef markA(x, y):if not sokkelo[y][x]:sokkelo[y][x] = 2for 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] = 3e = 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 RecursionErrorbuffer_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)returnif __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: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
(empty) |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
436 |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
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 |