解深度優先搜尋時，我們常用到

兩種方式來解，實際解題來看兩種差異。

1. 堆疊(stack)

2. 遞迴(recursion)

Leetcode 695 Max Area of Osland

題目：給一個m*n矩陣，矩陣中的值只有0或１，0代表海洋，1代表島嶼，找出陣列中為大島嶼的面積。

輸入：grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]

輸出：4

限制：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 50

• grid[i][j] is either 0 or 1.

堆疊解法：

1. 從頭找到尾檢查每一個矩陣中的值

2. 當值等於1，面積加1並將值改為0，並將四周位置加到堆疊(stack)

3. 判斷stack中的是否有連接島嶼，有的話面積加1，並持續step2對島嶼四周擴展，直到堆疊(stack)空了代表四周都是海了

4. 檢查完所有矩陣回傳最大面積

impl Solution {
    pub fn max_area_of_island(mut grid: Vec<Vec<i32>>) -> i32 {

        let mut stack = Vec::new();
        let mut max_area = 0;
        let mut current_area = 0;
        for m in 0..grid.len() {
            for n in 0..grid[m].len(){
                if(grid[m][n]==1){
                    current_area+=1;
                    grid[m][n]=0;
                    if ((m as i32 -1)>=0){
                        stack.push((m-1,n));
                    }
                    if ((m as i32 +1)<grid.len() as i32){
                        stack.push((m+1,n));
                    }
                    if ((n as i32 -1)>=0){
                        stack.push((m,n-1));
                    }
                    if ((n as i32 +1)<grid[m].len() as i32){
                        stack.push((m,n+1));
                    }
                    while let Some((m,n)) = stack.pop() {
                        if(grid[m][n]==1) {
                            current_area+=1;
                            grid[m][n]=0;
                            if ((m as i32 -1)>=0){
                                stack.push((m-1,n));
                            }
                            if ((m as i32 +1)<grid.len() as i32){
                                stack.push((m+1,n));
                            }
                            if ((n as i32 -1)>=0){
                                stack.push((m,n-1));
                            }
                            if ((n as i32 +1)<grid[m].len() as i32){
                                stack.push((m,n+1));
                            }
                        }
                    }
                    max_area=max_area.max(current_area);
                    current_area=0;
                }
            }
        }
        max_area
    }
}

遞迴解法：如Day10 Stack 函式呼叫我們把stack解法改成呼叫函式用系統堆疊來達到深度優先搜尋

impl Solution {
    pub fn max_area_of_island(mut grid: Vec<Vec<i32>>) -> i32 {
        let mut max_area = 0;
        //check every grid if value =1 do DFS get the island area
        for m in 0..grid.len() {
            for n in 0..grid[m].len() {
                    let current_area=Self::DFS(&mut grid, m, n);
                    max_area = max_area.max(current_area);
            }
        }
        max_area
    }

    pub fn DFS( grid: &mut Vec<Vec<i32>>, m:usize, n:usize) -> i32 {
        let mut total_area=0;

        if(grid[m][n]==1){
            total_area+=1;
            grid[m][n]=0;

            if (m as i32-1>=0){
                total_area+=Self::DFS(grid,m as usize -1,n);
            }
            if (m+1<grid.len()){
                total_area+=Self::DFS(grid,m+1,n);
            }
            if (n as i32 -1>=0){
                total_area+=Self::DFS(grid,m,n as usize -1);
            }
            if (n+1<grid[m].len()){
                total_area+=Self::DFS(grid,m,n+1);
            }
            return total_area
        } else{
            return 0
        }
    }
}

Day11總結

1. 使用stack來解深度優先