We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Implementation
  4. The Bomberman Game
  5. Discussions

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 image

      • 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 image

          • eric3141 + 1 comment

            Thanks!!
            Why couldn't the author of this challenge bother to give an example that covers all the steps? (Loops over steps 3,4.)

            • djglock + 0 comments

              I believe this is a part of the task :)

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

      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.

      • Abe10 + 0 comments

        Brilliant dude!!