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.

4

7 回答 7

2

到目前为止一切都很好。但修复以下

删除这两行：

i = a;
j = b;

如下调用它：

zeros( m, v, a, b);

代替：

zeros( m, v, i, j);

也改变这个：

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

也：

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

这样做是为了：

if(m[a][b] == 0 && v[a][b]==0)
于 2013-09-30T20:09:29.937 回答
2

考虑我使用运动常数的解决方案：

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

这是您从中移动的偏移量(x,y)。所以你的方法将是

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);
         }
    }               
}

例如，如果您(x=2,y=2)的邻居是：

(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)
于 2013-09-30T20:33:31.557 回答
1

这听起来与 Flood Fill 操作非常相似。维基百科有一些元代码来完成这一点。它不是递归的，但应该可以正常工作。

于 2013-09-30T20:09:14.383 回答
1

错误 java.lang.StackOverflowError 是处理递归时最常见的错误之一。这意味着您在递归中创建了一个无限循环，并且堆栈不足以处理所有递归调用。

想想当你在周围的方块上递归调用你的函数时会发生什么。因为您不编辑原始正方形，所以它会再次被调用，从而创建一个无限循环。

解决这个问题，你的问题就解决了。

于 2013-09-30T20:14:18.073 回答
0

我想我明白了。

只需在 fors 的 if 中添加这个额外的条件。

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

所以我们不能返回到矩阵视觉 v 中为 1 的任何位置

于 2013-09-30T20:40:17.837 回答
0

在执行“m[a][b] == 0”之前，您需要进行检查以确保 a 和 b 不在 m 的范围之外。我不认为你现在正在做那个检查。

于 2013-09-30T20:08:54.707 回答
0

您正在递归地传递 i 和 j，但您没有修改这些变量的值，因此调用将无限期发生

于 2013-09-30T20:17:02.917 回答