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

（一个完整的网站是一个开放的网站，可以将返回一个布尔值的方法通过周边（左，右，上，下）打开网站的链连接到开放的网站上的顶行）。

网格，真正=打开网站

我还在学习递归我读了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; 
}

来源

2013-03-14 user1189352

您不需要为第一个基本情况抛出异常，只需返回false即可。 – starhacker 2013-08-14 19:49:03

有这个website使用Java和递归的方法来检查，如果一个网格渗滤。还有另一种方法，通过使用“联盟查找”算法来检查：

/* 
    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-14 20:05:38 starhacker

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

回答

相关问题