1

ok, i have this function that needs to use recursion, to search in a mineswepper(int[][] m) given a coordinate(i, j) by the user, a zero. The zero means there is no mines near that localition. If it is a zero, then my function should show this zero and the zeros around this initial zero in a range of one localition. This has to be made in a recursive way, for all the zeros found.

My int[][]v is my vision matrix, it used to give and status(1 => you can show the location, 0 => keep the ?) for all the locations individually, so when i print all the matrix m we can only see the locations that have a 1 in the matrix v.

1-. Found a zero2

2-. Search around to find other zeros, until there is no more zero to found

?   ?   ?   ?
?   ?   ?   ?
?   ?   0   ?
?   ?   ?   ?
?   ?   ?   ?

how it would look like in the vision matrix v

0   0   0   0
0   0   0   0
0   0   1   0
0   0   0   0
0   0   0   0



?   ?   ?   ?
?   ?   ?   ?
?   ?   0   ?
?   ?   ?   0
?   ?   ?   ?

how it would look like in the vision matrix v

0   0   0   0
0   0   0   0
0   0   1   0
0   0   0   1
0   0   0   0

 public void zeros(int[][]m, int[][]v, int j, int i){

            v[i][j] = 1;

            for(int a = Math.max(0, i-1); a < Math.min(5,i+2); a++){
              for(int b = Math.max(0,j-1); b < Math.min(5,j+2); b++){
                 if(m[a][b] == 0){
                     i = a;
                     j = b;
                    zeros( m, v, i, j);}

                }
            }         
   }

The fors are to searh in all the locations around the given i and j.

It shows me errors, Exception in thread "main" java.lang.StackOverflowError. I dont get it why. Maybe someone could give a way eary to make the recursivity, or tell me my mistake.

Improve this question
4
  • Please demonstrate what you have tried and how it has failed. Commented Sep 30, 2013 at 20:04
  • You have a 5x4 matrix, so the indexes go from 0 to to 4 in one direction and from 0 to 3 in other direction. Maybe the error is that you are using an index 5, that is out of your matrix. Commented Sep 30, 2013 at 20:06
  • @angel_navarro No, the OP is getting a StackOverflowError, not an ArrayIndexOutOfBoundsException. Commented Sep 30, 2013 at 20:12
  • I think you are passing i and j recursively, but you don't modify the values of these variables, so the call will occur indefinitely. This fills the calls stack and it overflows ;-) Commented Sep 30, 2013 at 20:18

7 Answers 7

Reset to default
2

so far all good. but fix the following

remove those two lines:

i = a;
j = b;

call it as follow:

zeros( m, v, a, b);

instead of:

zeros( m, v, i, j);

also change this:

public void zeros(int[][]m, int[][]v, int j, int i)

too:

public void zeros(int[][]m, int[][]v, int i, int j)

do this to:

if(m[a][b] == 0 && v[a][b]==0)
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

i = a, j = b. is the main problem here. you are missing with the loop end conditions
Yepp! with the extra contion if(m[a][b] == 0 && v[a][b]!= 1) Thanks for the correction.
2

Consider my solution using movement constant:

int [] movx ={-1, -1, -1, 0, 0, 1, 1, 1};
int [] movy ={-1, 0, 1, -1, 1, -1, 0, 1};

This are the offset you move from (x,y). So your method will be

public void zeros(int[][] m, int[][] v, int x, int y) {

    //Already visited?  
    if (v[x][y] == 1) return;

    //Mark as visited   
    v[x][y] = 1;

    for (int i = 0; i < 8; i++){
        //neighbors coordinates
        int nx = x + movx[i];
        int ny = y + movy[i];

         //check boundaries
         if (nx >= 0 && nx < m.length && ny >= 0 && ny < m[x].length){

             //if there is no mine check it
             if (m[nx][ny] == 0)
                 zeros(m, v, nx, ny);
         }
    }               
}

for example if you have (x=2,y=2) your neighbors will be:

(x=1,y=1)
(x=1,y=2)
(x=1,y=3)
(x=2,y=1)
(x=2,y=2)
(x=2,y=3)
(x=3,y=1)
(x=3,y=2)
(x=3,y=3)
Improve this answer

3 Comments

you took only 4 neighbours. may be this is right. but our friend took 8.
@hasan yes, I fix it, sorry
nice solution I solved similar problem almost 100 time. used to write same as your solution with a little change.
1

This sounds very similar to a Flood Fill operation. Wikipedia has some meta-code to accomplish this. It's not recursive, but should work well.

Improve this answer

Comments

1

The error java.lang.StackOverflowError is one of the most common ones when dealing with recursion. It means that you created an infinite loop in your recursion, and the stack isn't big enough to handle all the recursive calls.

Think about what happens when you recursively call your function on surrounding squares. Because you don't edit the original square, it get's called again, creating an infinite loop.

Fix this and your problem is solved.

Improve this answer

Comments

0

Before you do "m[a][b] == 0", you need to do a check to make sure that a and b aren't outside the bounds of m. I don't think you're doing that check currently.

Improve this answer

1 Comment

he did with max and min functions
0

You are passing i and j recursively, but you don't modify the values of these variables, so the call will occur indefinitely

Improve this answer

Comments

0

I think that i get it.

just adding this extra condition in the if of the fors.

if(m[a][b] == 0 && v[a][b]!= 1)

so we can not return to any location that has a 1 in the matrix vision v

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.