0

我正在尝试编写一个布尔方法，如果矩阵是“满”的，它将返回

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

对于网格，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;
}
4

1 回答 1

1

有这个网站使用 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检查底部和顶部是否连接。

于 2013-08-14T20:05:38.627 回答