Sort 261 Discussions, By:
Please Login in order to post a comment
Did anyone also find this contradicting?
The question says thats when the bomb goes, it takes out anything in the four neighboring cells (top, bottom, left and right).
But in the example that follows, all the rest bombs in the 3x3 matrix are taken out by the one in the center.
Shouldn't the four corner ones be spared at second 3?
I solved the problem using the following tricks. I guess my solution is not perfect but I hope it can help who struggled.
Assume using the following time:
N = 0 (initial board - time of bomb is 3)
N = 1 (do nothing - time of bomb is reduced to 2)
N = 2 (time of existing bombs is reduced to 1, add new bombs to empty cells with time 3)
N = 3 (boms with time 1 will exploded, new boms added in previous steps have time reduced to 2).
I use the following test to illustrate my algorithm.
I convert it to the following arrays in my solution:
3 0 0 3
0 3 0 0
0 0 0 0
(3 is bomb with time 3. 0 is empty cells i.e has no bombs).
Below are some observation:
1/ When N = 4, N = 6, ..., board is full of bombs.
2/ Board at N = 3 is the same with board at N = 7, N = 11
3/ Board at N = 5 is the same with board at N = 9, N = 13
4/ To solve board at N = 3. Calculate board at N = 2
Given example a board with
N = 0 N = 2
3 0 0 3 1 3 3 1
0 3 0 0 -> 3 1 3 3
0 0 0 0 3 3 3 3
After 1 second (N = 3), cell with 1 will explode to 0 and make neighbour cells become 0. Cells with 3 become 2.
N = 3
0 0 0 0
2 0 2 2
5/ To solve board at N = 5. Use board at N = 3.
N = 3 N = 5
0 0 0 0 2 2 2 2
0 0 0 0 -> 0 2 0 0
2 0 2 2 0 0 0 0
Note that cells with 0 become 2 and cells with 2 become 0. This is because
- cells with 0 is empty cells and it will be populated with bombs at previous step (N = 4).
- cells with 2 is bomb cells and it will explode to 0 and make neighbour cells become 0.
Whoever created this problem clearly has never played Bomberman. #IJS
I made this little .html to help me visualize the problem, you can set the rows, columns and initial bombs position and watch it evolve. I hope you find it useful.
This is the JSFiddle with the same file
A few useful tricks for this problem:
If N = 1, then we just print the initial board, as Bomberman hasn't put any new bombs on it;
If we look at the board starting from second N = 2, we'll see a pattern. On every even time N, Bomberman will fill the empty spaces with bombs and, on every odd time N, he will observe some of them exploding. Then, without doing any unnecessary computation, we can say for sure that, if N is even, then the board will be full of bombs;
If you look at the remaining possible values of N (N >= 3 and N is odd), you'll see that there's a very clear pattern. Thanks to it, you can assure that there are only two possibilities of board configurations for those values and deciding between them is as easy as applying a simple math operator to N;
Using these previous 3 tips, you can simplify your problem. Instead of keeping track of the number of seconds remaining for a bomb to detonate, you can just keep an eye on those that will explode next.