Plant Poison Spread

ApplePhone screenMedium

A field of plants is an m x n grid. 0 is a healthy plant and 1 is a poisoned one. The neighbors of a plant are the up to 8 plants around it, horizontally, vertically and diagonally; plants on an edge or in a corner have fewer.

Each day, every healthy plant with at least k poisoned neighbors becomes poisoned. All plants change at the same moment: what happens on a day depends only on the field as it was at the start of that day. A plant that turns poisoned on a day counts as a poisoned neighbor from the next day on. Poisoned plants stay poisoned.

Part 1: Day-by-day spread

Given the initial field grid and threshold k, return the number of days on which at least one plant becomes poisoned, that is, the days until the field stops changing. If no plant ever turns poisoned, return 0.

Example 1
k
2
grid
[[0,1,1,0],[0,0,0,0],[0,0,0,0]]
Output
3
Why: On day 1 the two cells under the poisoned pair each touch two poisoned plants, so they turn. On day 2 the top corners, the left and right cells of the middle row and the two bottom-middle cells each touch two poisoned plants. On day 3 the bottom corners touch three. After that nothing changes, so the answer is 3.

Constraints

1 <= m <= 500 where m = len(grid)
1 <= n <= 500 where n = len(grid[0])
grid[i][j] is 0 or 1
1 <= k <= 8

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question