QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335309 | #5582. Chocolate Chip Fabrication | mfshi03 | TL | 13ms | 10452kb | Python3 | 1.0kb | 2024-02-23 09:01:22 | 2024-02-23 09:01:22 |
Judging History
answer
import collections
n, m = map(int, input().split())
tree = [["-"]*(m+2)] + [list("-" + input() + "-") for i in range(n)] + [["-"]*(m+2)]
# print(tree)
dp = [[float('inf') for i in range(m+2)] for j in range(n+2)]
# print(dp)
queue = collections.deque((i,j) for i in range(n+2) for j in range(m+2) if tree[i][j] == "-")
for i, j in queue:
dp[i][j] = 0
m += 2
n += 2
highest = 0
while queue:
node = queue.popleft()
r = float('inf')
i, j = node
if i-1 != -1 and dp[i-1][j] == float('inf'):
dp[i-1][j] = dp[i][j]+1
queue.append((i - 1, j))
if j-1 != -1 and dp[i][j-1] == float('inf'):
dp[i][j-1] = dp[i][j]+1
queue.append((i, j-1))
if i+1 != n and dp[i+1][j] == float('inf'):
dp[i+1][j] = dp[i][j]+1
queue.append((i + 1, j))
if j+1 != m and dp[i][j+1] == float('inf'):
dp[i][j+1] = dp[i][j]+1
queue.append((i, j+1))
dp[i][j] = min(dp[i][j], r)
if dp[i][j] > highest:
highest = dp[i][j]
print(highest)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 10300kb
input:
5 5 -X-X- XXXXX XXXXX -XXX- --X--
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 12ms
memory: 10396kb
input:
4 5 --XXX --X-X X-XXX XX---
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 10ms
memory: 10336kb
input:
5 5 XXXXX XXXXX XXXXX XXXXX XXXXX
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 9ms
memory: 10292kb
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: 13ms
memory: 10300kb
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: 13ms
memory: 10236kb
input:
3 4 XXXX -XXX XXXX
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 13ms
memory: 10300kb
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: 10432kb
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: 12ms
memory: 10316kb
input:
1 1 X
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 6ms
memory: 10396kb
input:
3 3 XXX XX- XXX
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 9ms
memory: 10316kb
input:
2 3 XXX XX-
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 6ms
memory: 10452kb
input:
3 1 - - X
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 12ms
memory: 10332kb
input:
2 2 XX -X
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 12ms
memory: 10416kb
input:
2 2 -- -X
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 13ms
memory: 10336kb
input:
2 2 XX XX
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 9ms
memory: 10336kb
input:
3 5 XXX-X XXXXX X-XXX
output:
2
result:
ok single line: '2'
Test #17:
score: 0
Accepted
time: 13ms
memory: 10396kb
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...