# The Bomberman Game

# The Bomberman Game

baranoob + 10 comments 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.

4 3

O..O

.O..

....

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

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.

anuragb26 + 0 comments [deleted]anuragb26 + 1 comment Hi, Can you please help me with the line " Board at N = 3 is the same with board at N = 7, N = 11". I have tried simulating till seven seconds but I don't get the same board.I have attached an image for my simulation

baranoob + 1 comment Hi anuragb26,

I tried to understand the context of your quesiton. Here are few comments:

In your image: the bomb at 1 second has 2 seconds left to explode.

At 2 second:

3 3 3 3 3 3 3

3 3 3 1 3 3 3

3 3 3 3 1 3 3

3 3 3 3 3 3 3

1 1 3 3 3 3 3

1 1 3 3 3 3 3

At 3 second:

3 3 3 0 3 3 3

3 3 0 0 0 3 3

3 3 3 0 0 0 3

0 0 3 3 0 3 3

0 0 0 3 3 3 3

0 0 0 3 3 3 3

At 4 second:

2 2 2 3 2 2 2

2 2 3 3 3 2 2

2 2 2 3 3 3 2

3 3 2 2 3 2 2

3 3 3 2 2 2 2

3 3 3 2 2 2 2

Could you please try until 7 second?

anuragb26 + 2 comments Thanks a lot !!..I was actually making a mistake at the fifth second..this method of replacing the question symbols with timer cleared it up For any one else, please see the image for reference

AGRN96 + 0 comments Thank you very much for placing these images of the simulation, it helped me notice a pattern in the outputs of my program.

https://www.hackerrank.com/challenges/bomber-man/submissions/code/41610838

The array only changes up to the 5th (n), from there it loops -> 5, 2, 3, 2 -> over and over again.

AAR_KAY + 0 comments thanks dude helped a lot

tmosest + 0 comments Thanks man!!!!! I didn't use you number matrix but your explanation allowed me to pass test 10 to 24!

29abhishekmittal + 2 comments Hi,

I understand the pattern but I could not understand how one can come up with this pattern.

It may happen that pattern holds true for some particular configuration of grid but not the other.

How one can prove that this pattern holds true for every possible grid configuration.

Thanks and Regards, Abhishek Mittal

Kevinagin + 0 comments Here's one way to see that the pattern holds regardless of the grid configuration.

Let's say an explosion takes place in cell c at time t = 5. That explosion would have wiped out c along with all of c's neighbors. Because we wiped out all of the neighbors, there's nothing left to stop the next bomb at c from going off four seconds later, at t = 9.

So more generally, once an explosion takes place in a cell, that cell is guaranteed to explode every 4 seconds from then on.

The first explosion takes place at t = 3. So that's why we repeat once we reach 3 seconds.

sharmaparthyoge1 + 1 comment import java.io.

*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*;public class Solution {

`// Complete the bomberMan function below. static String[] bomberMan(int n, String[] grid) { String[] ans = new String[grid.length]; int aa = grid[0].length(); String ab = ""; //String[] grd = new String(grid.length); for(int i=0;i<aa;i++){ ab = ab.concat("0"); } if(n%2 == 0){ for(int i=0;i<grid.length;i++){ ans[i] = ab; } } else{ if(n==1){ ans = grid; } else{ int count = 0; while(count<2){ for(int i=0;i<grid.length;i++){ char[] tmp1 = grid[i].toCharArray(); for(int j=0;j<aa;j++){ if(tmp1[j] == 'O'){ tmp1[j] = '1'; } else if(tmp1[j] == '.'){ tmp1[j] = 'O'; } } String ala = new String(tmp1); grid[i]=ala; } int flag = 0; int flag1 = 0; for(int i=0;i<grid.length;i++){ char[] tmp = grid[i].toCharArray(); char[] tm2 = grid[i].toCharArray(); char[] tm3 = grid[i].toCharArray(); if(i-1 != -1){ tm2 = grid[i-1].toCharArray(); } else{ flag = 1; } if(i+1 != grid.length){ tm3 = grid[i+1].toCharArray(); } else{ flag1 = 1; } for(int j=0;j<aa;j++){ if(flag == 0 && flag1 == 0){ if(tmp[j] == '1'){ tmp[j] = '.'; if(j!=0){ tmp[j-1] = '.'; } if(j!=tmp.length-1){ if(tmp[j+1] == 'O'){ tmp[j+1] = '.'; } } if(tm3[j] == 'O'){ tm3[j] = '.'; } if(tm2[j] == 'O'){ tm2[j] = '.'; } } } else if(flag == 1 && flag1 == 0){ //flag = 0; if(tmp[j] == '1'){ tmp[j]='.'; if(j!=0){ tmp[j-1] = '.'; } if(j!=tmp.length-1){ if(tmp[j+1] == 'O'){ tmp[j+1] = '.'; } } if(tm3[j] == 'O'){ tm3[j] = '.'; } } } else if(flag1 == 1 && flag == 0){ //flag1 = 0; if(tmp[j] == '1'){ tmp[j]='.'; if(j!=0){ tmp[j-1] = '.'; } if(j!=tmp.length-1){ if(tmp[j+1] == 'O'){ tmp[j+1] = '.'; } } if(tm2[j] == 'O'){ tm2[j] = '.'; } } } else{ if(tmp[j] == '1'){ tmp[j]='.'; if(j!=0){ tmp[j-1] = '.'; } if(j!=tmp.length-1){ if(tmp[j+1] == 'O'){ tmp[j+1] = '.'; } } } } } String a3 = new String(tmp); grid[i] = a3; if(flag == 0 && flag1 == 0){ String a1 = new String(tm2); String a2 = new String(tm3); grid[i-1] = a1; grid[i+1] = a2; } else if(flag == 1 && flag1 == 0){ //String a1 = new String(tm2); String a2 = new String(tm3); grid[i+1] = a2; flag = 0; } else if(flag == 0 && flag1 == 1){ String a1 = new String(tm2); //String a2 = new String(tm3); grid[i-1] = a1; flag1 = 0; } } count++; ans = grid; if((n+1)%4==0){ //grd = grid; break; } } } } return(ans); } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] rcn = scanner.nextLine().split(" "); int r = Integer.parseInt(rcn[0]); int c = Integer.parseInt(rcn[1]); int n = Integer.parseInt(rcn[2]); String[] grid = new String[r]; for (int i = 0; i < r; i++) { String gridItem = scanner.nextLine(); grid[i] = gridItem; } String[] result = bomberMan(n, grid); for (int i = 0; i < result.length; i++) { bufferedWriter.write(result[i]); if (i != result.length - 1) { bufferedWriter.write("\n"); } } bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); }`

}

Abhiskek The pattern is like if n=1 ans = grid if n%2 == 0 than all are 0's now the headache is when it is other than above cases I. For all cases the solution for n = 3,7,11,15....(i.e. the configration of grid at n=3) is same while for n = 5,9,13.... it is same as that of initial i.e. at t=1.

II. While for the second case it is like, for n = 3,7,11,15.... the solution is still same as that of the n=3 while for n = 5,9,13.... it is different from that of t=1 or initital. But for all n E (5,9,13,17...) it is same. So for worst case you need to follow the pattern mentioned(i.e. {i,j} = 0 will affect {i+-1 and j+-1}) in question for 2 times i.e. first time to find the grid for n=3,7,11... and second time for n=5,9,13,17... !!

I am not able to figure out for what cases of n=5,9,13,17..... we have to use I and for what cases II.

Hope it will be helpful for u.

jagadeesh52423 + 0 comments You should have use modularization. Create a function process and return, use it how many times you want.

laianbinh + 0 comments that is very itelligent. i did not think that it could be in a circle. thanks a lot.

_dec0der_ + 3 comments int m,n; char str[202][202],str1[202][202],str2[202][202],str3[202][202]; //Total 3 Patterns Repeatitve //str1 full of bombs //str2 detonate bombs in input //str3 detonate bombs in str2 int main() { int t; cin>>m>>n>>t; for(int i=0;i<m;i++) cin>>str[i]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) { str1[i][j]='O'; str2[i][j]='O'; str3[i][j]='O'; } //Processing for 1st Pattern using Input for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(str[i][j]=='O') { str2[i][j]='.'; if(i<m-1) str2[i+1][j]='.'; if(i>0) str2[i-1][j]='.'; if(j<n-1) str2[i][j+1]='.'; if(j>0) str2[i][j-1]='.'; } } } //Processing for 2nd Pattern using 1st Pattern for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(str2[i][j]=='O') { str3[i][j]='.'; if(i<m-1) str3[i+1][j]='.'; if(i>0) str3[i-1][j]='.'; if(j<n-1) str3[i][j+1]='.'; if(j>0) str3[i][j-1]='.'; } } } if(t==1||t==0) { for(int i=0;i<m;i++) cout<<str[i]<<"\n"; return 0; } if((t-1)%4==0) for(int i=0;i<m;i++) cout<<str3[i]<<"\n"; else if((t-1)%2==0) for(int i=0;i<m;i++) cout<<str2[i]<<"\n"; else for(int i=0;i<m;i++) cout<<str1[i]<<"\n"; return 0; }

RishabhKejariwal + 0 comments while using this same logic in c, the output gets truncated after few lines. Please Help

qwrtyuiuytres + 1 comment logical str3 and str both r same.but, when i remove str3 .tc fails, why?

santhoshvillerss + 1 comment yaa bro i also don't know why it is happening

alaymehta10 + 0 comments No they are not same ....just see some examples above in comments and u will know

SL170040869 + 0 comments so much helpful

Zyro9922 + 0 comments [deleted]JuniorStudent + 0 comments Thanks, i were confusing to figured it out. when i read your explanation, i got the idea, that's find the pattern by simulate it, then turn it into code. finally i passed all tc at first strike :')

sarathy_v_krish1 + 1 comment C++ solution :

vector<string> bomberMan(int n, vector<string> grid) { vector<string> set1=grid, set2, set3; for (int i=0;i<grid.size();i++) for (int j=0;j<grid[0].size();j++) set1[i][j]='O'; set2=set3=set1; for (int i=0;i<grid.size();i++) for (int j=0;j<grid[0].size();j++) if (grid[i][j]=='O') { if (i>0) set2[i-1][j]='.'; if (i<grid.size()-1) set2[i+1][j]='.'; if (j>0) set2[i][j-1]='.'; if (j<grid[0].size()-1) set2[i][j+1]='.'; set2[i][j]='.'; } for (int i=0;i<grid.size();i++) for (int j=0;j<grid[0].size();j++) if (set2[i][j]=='O') { if (i>0) set3[i-1][j]='.'; if (i<set2.size()-1) set3[i+1][j]='.'; if (j>0) set3[i][j-1]='.'; if (j<set2[0].size()-1) set3[i][j+1]='.'; set3[i][j]='.'; } /*cout << "Printing grid, set1, set2 : \n"; for (int i=0;i<grid.size();i++) cout << grid[i] << endl; cout << endl << endl; for (int i=0;i<grid.size();i++) cout << set1[i] << endl; cout << endl << endl; for (int i=0;i<grid.size();i++) cout << set2[i] << endl;*/ if (n%2==0) return set1; if (n==1) return grid; if (n%4==3) return set2; return set3; }

bng442 + 1 comment whats your logic behind this:

`if (n%2==0) return set1; if (n==1) return grid; if (n%4==3) return set2; return set3;`

sarathy_v_krish1 + 0 comments The idea to grasp is that after the first time instant (n=1), the grid keeps toggling between 3 possible configurations.

So after generating the 3 patterns, we need to notice that the patterns keep repeating in the order(set no.) : . . . . . . . . 3 1 2 1 3 1 2 1 3 1 2 1 . . . . . . . . with a net frequency of 4

So if n is even, print set 1.

If n is odd and n%4 is 1, print set 3.

If n is odd and n%4 is 3, print set 2.

wangyu601 + 5 comments 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?SilentZebra + 0 comments I would assume that one is a typo. Go with what's in the description and what's shown in the following examples - just the four adjacent bombs and the existing bomb. Worked for me

fabio_guggeri + 1 comment I came to the comments for the same reason. The text should be updated.

nichijou + 0 comments never~

IntezarAlam + 0 comments Yes...It is contradicting.

Kalki_SEAS + 0 comments I too observed

blakesterburt + 1 comment I informed them of the error. We'll see if it's corrected or not.

haitao_fu_41 + 0 comments [deleted]

yanr_dasilva + 1 comment 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.

nvzee + 0 comments Nice job figuring the pattern for odd epochs. I had a feeling somthing like this should be the case on reading the comments I decided to simulate and check it out!

mingmingrr + 1 comment Watch out for transient bombs!

Example:

o.o. oooo .... oooo oooo oooo .... .o.o -> oooo -> .... -> oooo -> oooo -> oooo -> .... -> etc o.o. oooo .... oooo oooo oooo ....

harshankur + 0 comments thanks for the tip!

guillermogotre + 2 comments 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

sharmaparthyoge1 + 0 comments Bro that one was really nice

codertoaster + 0 comments Really nice. But all that work to illustrate the wrong logic. The whole 33 matrix blows up and not just the 4 cells at the top, bottom, left and right. That's a typo in the question.

brunolm + 0 comments This might help

sanjitschouhan + 3 comments Every fifth second you get board of first second so for

*n>4*seconds you can take*n=4+n%4*I didnt understood why it is working when adding 4 but not when taking without it. If anyone have any idea do comment.Suvansh + 1 comment I also got the same problem, that took a lot of time... but even then, ONLY 2nd test case is remaining, which shows wrong answer... I don't know why

sanjitschouhan + 2 comments For me all cases passed. Try adding 4 to n mod 4 whenever n is greater than 4. This may be because first four cases are unique and next four repeats every time.

eric3141 + 0 comments I found it useful to output a hash of the printed state, to make the cycle clear.

./bomber-man -verbose <input |grep Hash SHA1 Hash: 6c0d0d164f7bf82af5fc60973449582af40a71d1 // first in cycle SHA1 Hash: d159e684e482359576216bba0e5ba63b569b2f79 SHA1 Hash: 41eab4fd163ddd5262483a62003f8ff17e89e8f7 SHA1 Hash: d159e684e482359576216bba0e5ba63b569b2f79 SHA1 Hash: 6c0d0d164f7bf82af5fc60973449582af40a71d1 // first in cycle SHA1 Hash: d159e684e482359576216bba0e5ba63b569b2f79 SHA1 Hash: 41eab4fd163ddd5262483a62003f8ff17e89e8f7 SHA1 Hash: d159e684e482359576216bba0e5ba63b569b2f79 SHA1 Hash: 6c0d0d164f7bf82af5fc60973449582af40a71d1 // first in cycle ...

[deleted] + 1 comment [deleted]bhavikgevariya + 0 comments n = n - ( ( (n-1) / 4 ) * 4 )

wild_fire + 0 comments [deleted]khalimudin + 0 comments thanks, I pass all test now

abhinavdhoka + 0 comments Spoiler alert!! To reduce execution time of your code.. Use n=n%4+4;(Helped me in passing 11 test cases) Explaination :- You will find that after the first 5 stages(seconds) , all the stages will get repeated except for the first stage(Hence 4).

ramkumar_tce_cse + 0 comments Look for the pattern.

Sort 187 Discussions, By:

Please Login in order to post a comment