QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623140 | #5730. Maze Connect | TheZachMan | AC ✓ | 1113ms | 155208kb | Python3 | 1.3kb | 2024-10-09 10:21:03 | 2024-10-09 10:21:04 |
Judging History
answer
from collections import deque
r, c = map(int, input().split())
lines = []
for i in range(r):
lines.append(input())
st = None
for i in range(r):
for j in range(c):
if lines[i][j] != '.':
st = (i + j + (lines[i][j] == '\\')) % 2
break
if st != None:
break
if st == None:
st = 0
o = 0
exposed = {}
q = deque()
for i in range(1,r):
for j in range((i%2)+st,c,2):
q.append((i,j))
E = False
visited = {}
while len(q) > 0:
a, b = q.pop()
if (a,b) in visited:
continue
visited[a,b] = 0
if (a,b) in exposed:
E = True
q.clear()
break
if a <= 0 or a >= r or b <= 0 or b >= c:
E = True
q.clear()
break
if lines[a-1][b-1]=='.':
q.append((a-1,b-1))
if lines[a][b-1]=='.':
q.append((a+1,b-1))
if lines[a-1][b]=='.':
q.append((a-1,b+1))
if lines[a][b]=='.':
q.append((a+1,b+1))
if not E:
o += 1
for v in q:
visited[v]=0
q.clear()
for k in visited:
exposed[k]=0
print(o)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 10616kb
input:
2 2 /\ \/
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 4ms
memory: 10588kb
input:
4 4 /\.. \.\. .\/\ ..\/
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 16ms
memory: 10608kb
input:
2 2 \/ /\
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 12ms
memory: 10700kb
input:
8 20 /\/\/\/\/\/\/\/\/\/\ \../\.\/./././\/\/\/ /./\.././\/\.\/\/\/\ \/\/\.\/\/./\/..\../ /\/./\/\/./..\/\/..\ \.\.././\.\/\/./\.\/ /.../\../..\/./.../\ \/\/\/\/\/\/\/\/\/\/
output:
26
result:
ok single line: '26'
Test #5:
score: 0
Accepted
time: 556ms
memory: 75224kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
499001
result:
ok single line: '499001'
Test #6:
score: 0
Accepted
time: 558ms
memory: 75168kb
input:
1000 1000 \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...
output:
499000
result:
ok single line: '499000'
Test #7:
score: 0
Accepted
time: 874ms
memory: 84104kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
122943
result:
ok single line: '122943'
Test #8:
score: 0
Accepted
time: 24ms
memory: 11452kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ .............................................../....\........................................
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 23ms
memory: 11204kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ ..............................................././\.\........................................
output:
25
result:
ok single line: '25'
Test #10:
score: 0
Accepted
time: 16ms
memory: 10744kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #11:
score: 0
Accepted
time: 5ms
memory: 10804kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #12:
score: 0
Accepted
time: 13ms
memory: 10660kb
input:
21 21 /\/\/\/\/\/\/\/\/\/\. \...\...\...\...\...\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\....
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 1065ms
memory: 155208kb
input:
997 997 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 12ms
memory: 10704kb
input:
10 10 ..../\.... .../..\... .././\.\.. ././..\.\. /././\.\.\ \.\.\/././ .\.\.././. ..\.\/./.. ...\../... ....\/....
output:
3
result:
ok single line: '3'
Test #15:
score: 0
Accepted
time: 16ms
memory: 10708kb
input:
10 11 ...../\.... ..../..\... ..././\.\.. .././..\.\. ./././\.\.\ .\.\.\/././ ..\.\.././. ...\.\/./.. ....\../... .....\/....
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 1113ms
memory: 86932kb
input:
1000 1000 .....................................................................................................................................................................................................................................................................................................
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 19ms
memory: 11292kb
input:
100 100 ././././././././././././././././././././././././././././././././././././././././././././././././././ /./././././././././././././././././././././././././././././././././././././././././././././././././. ./././././././././././././././././././././././././././././././././././././././././././././...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 23ms
memory: 11168kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ \.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\. .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 15ms
memory: 11204kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ ././././././././././././././././././././././././././././././././././././././././././././././././././ .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 8ms
memory: 10588kb
input:
4 4 /\/\ \/\/ /\/\ \/\/
output:
5
result:
ok single line: '5'
Test #21:
score: 0
Accepted
time: 15ms
memory: 10764kb
input:
3 3 /\. \/\ .\/
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 909ms
memory: 84380kb
input:
1000 1000 \/..\../..\/\/./......./..././..\../.../....\.\/././......./././.../..........\...\/.../..\.\../......\.....\.\/..\.././..\...\/...../.../\/./..\.......\../..\/\/..\/...../..././\/./..././................\....../..\....../././.../....\...\/....\.\/......\.......\../.../....\.\/..\....../.....
output:
86
result:
ok single line: '86'
Test #23:
score: 0
Accepted
time: 437ms
memory: 45500kb
input:
1000 500 /\.\...\/\...././....././\.\.....\.\/././\../......\...\.\.......\/././....\.././......./.../.../\.........\/....\../..\.....\........../\/\.....\/......./..\/......./........\.....\...\...\/./...../..\/......\..../.........../..\.\...././..........\/././\......../\/........\....../\...\../...
output:
722
result:
ok single line: '722'
Test #24:
score: 0
Accepted
time: 14ms
memory: 11220kb
input:
100 100 \/\/\/\/\/.../.../\/\.\/\.\/\/.../././\.\../././\........../..\/..././.../..\.\.......\/\..../\..../ /./\/\.\/...../.../\..../\../..\/.../..././.../..\...\../\/\.\../\/././..\/...../....././....\/././\ \/\.\...\/....\/.../......\/\.\.\...\/..\.\/\/..\../..\...\/\/\/./\../....\/\/./.../\/\../...
output:
184
result:
ok single line: '184'
Test #25:
score: 0
Accepted
time: 50ms
memory: 14152kb
input:
250 250 /\............/..\........../.../....././\....../....\.....\............................../.../.../..........\...\....../....\...\/........\.\/./...../..........\..../............\..../....\...\.......././....\.\................../...../..\.\/..\.\/\ ..\...\/...../\...\.......\.\.\/./\.\/......
output:
6
result:
ok single line: '6'
Test #26:
score: 0
Accepted
time: 417ms
memory: 46124kb
input:
500 1000 /\.\/\../....\/\.\/..././.../\/....\.././\/..\.\/..\/..\...\...\/....././....\.\.\.\.\.././\/./..\/.../..\/..\.\/./....\/./..\...\/..\/.../\..../..\/..\.\.\.....\/.../..\.\...\.\/........\/./..\...\/./...../\.\/././....\/..\/./\.\.\/././\/..\/./.../\...././..\/././...../\/\../..\/./\../.......
output:
2762
result:
ok single line: '2762'
Test #27:
score: 0
Accepted
time: 203ms
memory: 27416kb
input:
500 500 \...\../..\...\/...../\....../..\.....././....\/.../........\...\...\/./.../..././.../......\../\/....\...\../..\...\/..........\.././...../...../..\...\...\..../..\.\.....\/............\...\/\/..\.............\....../\/.../././\.....././.../............\..../\/./..\.\......../..\.....\../.....
output:
663
result:
ok single line: '663'
Test #28:
score: 0
Accepted
time: 14ms
memory: 10820kb
input:
50 50 /\.\.\.\.././.../..././.../\.....\/..\/\.\...\.... ...../\.....\.\/./\/......./\..../..\/..\.\/./\../ ..../\.\/\..../..\.\../........\/....\.././\...\/\ \/\/././\...\/./\/........\.....\/\/./..\...\/\... ...\/...../\.........\/..\.\...\/.../.../\../..\.. \../....\../..\.././././\.\../...../......
output:
21
result:
ok single line: '21'