A Grass Field is divided into N x M Blocks of size 1. Some of the blocks in the field have caught fire. Now, in each second, the fire is spreading to the adjacent Blocks i.e. if (i , j) Block is on fire at time t, then Blocks (i + 1, j) , (i - 1, j) , (i , j - 1) , (i , j + 1) will be on fire at time t+1.
We will be provided with the current configuration of the field at time t = 0. Our task is to determine the minimum time in which the whole field catches fire. M[i][j] = 1 , if the block is on fire. M[i][j] = 0 , if the block is not on fire.
Example:
0 0 0
0 1 0
0 0 0
Answer:
2
According to me we have to check diagonals.
Can somebody help me in this.
How can we solve it for general case.
I found this to be an interesting problem and devised a solution for the simple case of one initial square being on fire, although I believe this solution can be extended to any number of initial squares being set on fire.
On a high level, I broke this problem down into a subproblem that I knew I could solve every time. To do this, I found the amount of time to fill the field if the initial square on 'fire' was in one of the four corners. Through utilizing the $L_1$ norm (or taxicab distance metric as mentioned above) this becomes trivial.
For any matrix $M$ of size $(n,m)$, given that a singular corner is on fire, the time $t$ taken to fill the whole matrix is given by: $t=n+m-2$. This is a direct application of the $L_1$ distance, where we subtract two, one for the initial square on fire and one for the corner so it doesn't double count. Writing out a small example of something less than $(10x10)$ helped me see what was going on.
From there there we just notice that if only one square starts on fire anywhere in our matrix/field, we can then break our matrix $M$ into 4 sub-fields, where each has a singular corner on fire. From there we know the time each of the four sub fields will take to burn, which we can call $t_1, t_2, t_3,$ and $t_4$. Thus the minimum time it takes the whole field to burn is going to be the longest burning sub-field, defined as $max(t_1, t_2, t_3, t_4)$.
I didn't spend a lot of time on this but after coding up both the problem and my solution and running it 1000 times on randomly generated field sizes and initial points, it worked every time.
I believe this problem also has relation to Voroni Cells, and I believe this solution could be adapted to multiple starting points.