Zombie in Matrix Lintcode - 璨璨要好好学习 - 博客园

Zombie in Matrix Lintcode - 璨璨要好好学习 - 博客园

Zombie in Matrix Lintcode

Given a 2D grid, each cell is either a wall 2, a zombie 1or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.

Example

Given a matrix:

0 1 2 0 0  1 0 0 2 1  0 1 0 0 0  

return 2

In this question, I store i * m + j in the queue, and m is the column number in the matrix.

 

In this question, pay attention that I should count the day first, becasue in the last day, everyone is zombie but if I don't return the day, the queue will keep iterate because it is not empty. For example, if I return the day number in the first day, the day should be 1. So add the day at first.

 

And pay attention that I can count the people first so if it drop to 0 I can return directly.

Read full article from Zombie in Matrix Lintcode - 璨璨要好好学习 - 博客园