QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335311#5582. Chocolate Chip Fabricationmfshi03TL 13ms10400kbPython31.2kb2024-02-23 09:02:472024-02-23 09:02:47

Judging History

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

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

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

output:


result: