QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335311 | #5582. Chocolate Chip Fabrication | mfshi03 | TL | 13ms | 10400kb | Python3 | 1.2kb | 2024-02-23 09:02:47 | 2024-02-23 09:02:47 |
Judging History
answer
from collections import deque
def iter_neighbors(loc):
yield (loc[0] + 1, loc[1])
yield (loc[0], loc[1] + 1)
yield (loc[0] - 1, loc[1])
yield (loc[0], loc[1] - 1)
height, width = map(int, input().split())
G = [[-1 for _ in range(width)] for _ in range(height)]
Q = deque()
m = 0
for row in range(height):
for col, c in enumerate(input()):
if c == '-':
G[row][col] = 0
Q.append((row,col))
for i in range(height):
if G[i][0] == -1:
G[i][0] = 1
Q.append((i,0))
m = 1
if G[i][width-1] == -1:
G[i][width-1] = 1
Q.append((i,width-1))
m = 1
for i in range(width):
if G[0][i] == -1:
G[0][i] = 1
Q.append((0,i))
m = 1
if G[height-1][i] == -1:
G[height-1][i] = 1
Q.append((height-1,i))
m = 1
while len(Q) > 0:
spot = Q.popleft()
count = G[spot[0]][spot[1]]
for n in iter_neighbors(spot):
row, col = n
if row >= 0 and col >= 0 and row < height and col < width and G[row][col] == -1:
G[row][col] = count + 1
if count + 1 > m: m = count + 1
Q.append(n)
print(m)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 10364kb
input:
5 5 -X-X- XXXXX XXXXX -XXX- --X--
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 12ms
memory: 10252kb
input:
4 5 --XXX --X-X X-XXX XX---
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 13ms
memory: 10364kb
input:
5 5 XXXXX XXXXX XXXXX XXXXX XXXXX
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 12ms
memory: 10400kb
input:
9 9 ----X---- ----X---- ----X---- ---XXX--- XXXXXXXXX ---XXX--- ----X---- ----X---- ----X----
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 5ms
memory: 10344kb
input:
7 7 --X-X-- --X-X-- XXXXXXX --X-X-- XXXXXXX --X-X-- --X-X--
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 12ms
memory: 10276kb
input:
3 4 XXXX -XXX XXXX
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 12ms
memory: 10260kb
input:
10 10 XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 12ms
memory: 10288kb
input:
10 10 XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXX-XXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 9ms
memory: 10388kb
input:
1 1 X
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 12ms
memory: 10276kb
input:
3 3 XXX XX- XXX
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 12ms
memory: 10236kb
input:
2 3 XXX XX-
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 12ms
memory: 10176kb
input:
3 1 - - X
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 12ms
memory: 10276kb
input:
2 2 XX -X
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 8ms
memory: 10228kb
input:
2 2 -- -X
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 13ms
memory: 10268kb
input:
2 2 XX XX
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 9ms
memory: 10240kb
input:
3 5 XXX-X XXXXX X-XXX
output:
2
result:
ok single line: '2'
Test #17:
score: 0
Accepted
time: 12ms
memory: 10356kb
input:
4 5 XXXXX XXX-X X-XXX XXXXX
output:
1
result:
ok single line: '1'
Test #18:
score: -100
Time Limit Exceeded
input:
1000 1000 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...