QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688203#5582. Chocolate Chip FabricationTenshi#TL 15ms10724kbPython3954b2024-10-30 00:28:552024-10-30 00:28:56

Judging History

你现在查看的是最新测评结果

  • [2024-10-30 00:28:56]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:10724kb
  • [2024-10-30 00:28:55]
  • 提交

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...

output:


result: