使用深度優先搜索遍歷矩陣找出滲流

Question

我想寫如果一個矩陣是「完全」或不

（一個完整的網站是一個開放的網站，可以將返回一個布爾值的方法通過周邊（左，右，上，下）打開網站的鏈連接到開放的網站上的頂行）。

網格，真正=打開網站

我還在學習遞歸我讀了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和遞歸的方法來檢查，如果一個網格滲濾。還有另一種方法，通過使用「聯盟查找」算法來檢查：

/* 
    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檢查，如果底部和頂部連接。