leetcode算法總結 —— DFS之網格類問題

文章目錄

• • 網格類DFS
  • • 1. 周遊過的島嶼需要标記
    • 2. 周遊過的島嶼需要再次使用的情況

網格類DFS

我把此類問題歸納為網格類的DFS，典型例題為島嶼标記，下面是該體型類模版，類似題都是根據該模版變形。

模闆

1. 周遊過的島嶼需要标記

class Solution {
public:
    int numIslands(vector<vector<char>> &grid)
    {
        int count = 0;
        if (grid.size() == 0) return 0;
        //周遊網格
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                //如果該格子是1，則該1進行dfs得到連接配接的所有1組成一個島嶼
                if(grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;//組成島嶼後島嶼數量加一
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>> &grid, int row, int col) {
        //判斷是否到邊界,超過邊界則return
        if(row < 0 || row > grid.size()-1 || col < 0 || col > grid[0].size()-1) return;

        //如果目前為1則我們把它标記為2, 如果不是1則我們就return，該點不繼續遞歸
        //這裡走過的要做标記是為了防止回頭周遊，走過的就不走了
        if(grid[row][col] == '1') grid[row][col] = '2';
        else return;

        //上下左右遞歸
        dfs(grid, row-1, col);
        dfs(grid, row+1, col);
        dfs(grid, row, col-1);
        dfs(grid, row, col+1);
    }

};
           

• 1. 島嶼數量
• 1. 島嶼的周長
• 1. 島嶼的最大面積
• 1. 不同島嶼的數量
• 1. 圖像渲染
• 1. 被圍繞的區域
• 劍指 Offer 13. 機器人的運動範圍

2. 周遊過的島嶼需要再次使用的情況

上述幾個題周遊過的島嶼标記後就不會再次周遊，而下面幾題會在标記後再次使用，這就需要在後序周遊處使用回溯，将已标記的島嶼撤銷标記

//如果目前島嶼的下一個島嶼傳回true也就是找到了，則可以傳回了，不需要繼續遞歸了
        if( dfs(board, row-1, col, index) ||
        dfs(board, row+1, col, index) ||
        dfs(board, row, col-1, index) ||
        dfs(board, row, col+1, index) == true) {
            return true;
        }

        //回溯：這裡是後序周遊執行代碼，也就是說我們DFS一條ABC之後，會往回走一遍，也就是向父節點傳回
        //當往回走的時候，我們把目前節點值還原成原字元，因為後面再次查找路徑的時候會使用該字元
        board[row][col] = temp;
        return false;
    }
           

• 1. 單詞搜尋(注意這裡要判斷下一個島嶼，不然逾時)