java - 使用深度优先搜索遍历矩阵找出渗流

Question

我正在尝试编写一个 boolean 方法，该方法将返回矩阵是否“已满”

(完整站点是一个开放站点，可以通过一系列相邻(左、右、上、下)开放站点连接到顶行中的开放站点。)

对于网格，true = 打开站点

我仍在学习递归，并且我在某处读到 DFS 用于解决迷宫，所以我正在尝试该路线...

现在我刚刚添加了一个相同大小的矩阵来跟踪该地点是否已被访问过。我只是想找出一个办法。给定一个初始位置，看看我是否可以使用递归遍历到顶行..

我知道这是错误的，有人可以帮助指导我。我现在陷入困境，我有点沮丧。这就是我到目前为止所得到的

private boolean [][] grid;
private boolean [][] visited;
private int size;

public boolean isFull(int i, int j)
{
    int row = i-1;
    int col = j-1;


    //base cases        
    if(row < 0 || row > size || col < 0 || col > size) {
        throw new IndexOutOfBoundsException("Out of Bounds Exception");
    }

    if(row == 0) {
        return true;
    }

    if(visited[row][col]) {
        return false;
    }

    visited[row][col] = true;

    //top
    isFull(row, col-1);
    //bot
    isFull(row, col+1);
    //left
    isFull(row-1, col);
    //right
    isFull(row+1, col);

    return false;
}

Answer 1

有这个website它使用 java 和递归方法来检查网格是否渗透。还有另一种检查方法，即使用“Union Find”算法:

/*
    To start and for convenience, set each elements's
    id to its own index value
*/

//number of elements to test
int n; 

int[] treeSize = new int[n];
int[] id = new int[n];
for(int i = 0; i < n; i++){
    id[i] = i;
    treeSize[i] = 1;
}

void makeUnion(int p, int q){
    /*
       Connect smaller tree to the bigger one by
       making root of the smaller tree the child of
       the root of the bigger tree.
    */
    int pRoot = getRoot(p);
    int qRoot = getRoot(q);

    treeSize[pRoot] < treeSize[qRoot] ?
      id[pRoot] = qRoot, treeSize[qRoot] += treeSize[pRoot] :
      id[qRoot] = pRoot, treeSize[pRoot] += treeSize[qRoot] ;
}

bool connected(int p, int q){
  return getRoot(p) == getRoot(q);
 }

int getRoot(int i){
   /*
     Transverse through parent
     pointers in the tree
     until root is reached
   */
   while(i != id[i]){         //check if root
      id[i] = id[ id[i] ];  //flatten tree a bit(path compression by 1/2) points to grand-parent now
      i = id[i];                          //move up one level
   }
   return i;
}

您迭代整个网格并使用 makeUnion连接两个点(如果它们开放且相邻)并使用 connected检查底部和顶部是否连接。