QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688203 | #5582. Chocolate Chip Fabrication | Tenshi# | TL | 15ms | 10724kb | Python3 | 954b | 2024-10-30 00:28:55 | 2024-10-30 00:28:56 |
Judging History
answer
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
grid = []
grid.append([False] * (m + 2))
for _ in range(n):
grid.append([False] + list(map(lambda x: True if x == "X" else False, input().strip())))
grid[-1].append(False)
grid.append([False] * (m + 2))
# for r in grid:
# print([1 if x else 0 for x in r])
import heapq
frontier = [(0, 0, 0)]
depths = [[float('inf') for j in range(m + 2)] for i in range(n + 2)]
while len(frontier) > 0:
depth, i, j = heapq.heappop(frontier)
if depth >= depths[i][j]:
continue
depths[i][j] = depth
for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
if i + di < 0 or j + dj < 0 or i + di >= n + 2 or j + dj >= m + 2:
continue
heapq.heappush(frontier, ((depth + 1 if grid[i + di][j + dj] else 0), i + di, j + dj))
# print()
m = 0
for r in depths:
# print(r)
m = max(max(r), m)
print(m)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 10496kb
input:
5 5 -X-X- XXXXX XXXXX -XXX- --X--
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 15ms
memory: 10688kb
input:
4 5 --XXX --X-X X-XXX XX---
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 13ms
memory: 10624kb
input:
5 5 XXXXX XXXXX XXXXX XXXXX XXXXX
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 7ms
memory: 10676kb
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: 15ms
memory: 10504kb
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: 11ms
memory: 10712kb
input:
3 4 XXXX -XXX XXXX
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 7ms
memory: 10724kb
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: 10ms
memory: 10596kb
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: 14ms
memory: 10712kb
input:
1 1 X
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 11ms
memory: 10572kb
input:
3 3 XXX XX- XXX
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 14ms
memory: 10608kb
input:
2 3 XXX XX-
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 5ms
memory: 10616kb
input:
3 1 - - X
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 10ms
memory: 10668kb
input:
2 2 XX -X
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 11ms
memory: 10552kb
input:
2 2 -- -X
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 10ms
memory: 10552kb
input:
2 2 XX XX
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 11ms
memory: 10616kb
input:
3 5 XXX-X XXXXX X-XXX
output:
2
result:
ok single line: '2'
Test #17:
score: 0
Accepted
time: 11ms
memory: 10624kb
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...