QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#335309#5582. Chocolate Chip Fabricationmfshi03TL 13ms10452kbPython31.0kb2024-02-23 09:01:222024-02-23 09:01:22

Judging History

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

  • [2024-02-23 09:01:22]
  • 评测
  • 测评结果:TL
  • 用时:13ms
  • 内存:10452kb
  • [2024-02-23 09:01:22]
  • 提交

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)

詳細信息

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

output:


result: