• En
• Signup
• # Amazon | OA 2019 | 🧟‍♀️ Zombie in Matrix

• 查看作者
• 打赏作者
• 拉黑名单
• Given a 2D grid, each cell is either a zombie `1` or a human `0`. Zombies can turn adjacent (up/down/left/right) human beings into zombies every hour. Find out how many hours does it take to infect all humans?

Example:

```Input:
[[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 1, 0, 0, 0]]

Output: 2Explanation:
At the end of the 1st hour, the status of the grid:
[[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 0, 1, 1],
[1, 1, 1, 0, 1]]

At the end of the 2nd hour, the status of the grid:
[[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]]```
`int minHours(int rows, int columns, List<List<Integer>> grid) {	// todo}`

Related problems:

```def minHour(rows, columns, grid):
times=0
Q=deque([])
directions=[[1,0],[-1,0],[0,1],[0,-1]]

for i in range(rows):
for j in range(columns):
if grid[i][j]==1:
Q.append((i,j))

while(Q):
for _ in range(len(Q)):
x,y=Q.popleft()
for dir in directions:
i=x+dir
j=y+dir
if 0<=i<rows and 0<=j<columns and grid[i][j]==0:
grid[i][j]=1
Q.append((i,j))
times+=1
return max(0,times-1)```

请登录之后再进行评论