Graph DFS/BFS: Leetcode 200: number of island

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

11110
11010
11000
00000

Answer: 1
Example 2:

11000
11000
00100
00011

Answer: 3

这个题目分析题目意思其实不难知道题目是求什么，如果能找到所有能连通的1的个数那么就是island的个数了，所以题目转化为求能连通的1的个数。  那么怎么求能连通的1的个数呢？
很显然要么是BFS， 要么是DFS，
如果是BFS来找，对一个‘1’的位置进行expand， 如果expand出来的都是' 0',说明已经找到了一个island， 继续去找另一个‘1’，继续找以它为扩充的island。

如果是DFS来找，连通的区域是一条路径可以走完的，所以是用的mark visit I, mark the node when first visit. 每次只走‘1’的位置，并且走到mark，当可以走到的1全部走完就说明走完了一个连通区域，继续找下一个‘1’。 而这里不需要用mark visit II （back-tracking）, 因为mark visit II用在需要遍历所有路径的时候， DFS+ mark visit I ==> BFS, 代码比BFS短，但是可能需要用的空间比BFS大，在分析优劣的时候要注意。

DFS 遍历 graph，一般的步骤是： 1. base case： 一般情况下，在遍历过程中，如果这个node已经visit过了，那么就return，依据题目的意思不同，可能还有其他的base case；2. mark current visiting node  to be visited 3. traverse the node in 4 directions. 如果是mark visit II，最后一步需要把current node mark成 unvisited.

DFS和BFS还有一点不同是， DFS在expand的时候是不需要在那个时候把node mark 成visited的。

BFS 遍历graph， 一般的步骤是： 1. push start node to queue, insert the start node into visited_set; 2. while (!queue.empty()) pop current node, 3. expand the node in 4 direction if unvisited, mark visit, push the node into queue.

class Solution {
private:
    void SearchIsland(int i, int j, vector<vector<char>> &grid) {
        //base caes
        if (grid[i][j] == '#') return; //if node has been visited, return
        if (grid[i][j] == '0') return;
        grid[i][j] = '#'; //mark visited II
        //no need to care about the visit state when expand, this can be checked before expand
        if (i+1 < grid.size()) SearchIsland(i+1, j, grid);
        if (i-1 >= 0) SearchIsland(i-1, j, grid);
        if (j-1 >= 0) SearchIsland(i, j-1, grid);
        if (j+1 < grid[0].size()) SearchIsland(i, j+1, grid);
        return;
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        //sanity check
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int rst = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1' ) {
                    SearchIsland(i, j, grid);
                    rst++;
                }
            }
        }
        return rst;
    }
};

BFS 解法：

class Solution {
private:
    void SearchIsland(int i, int j, vector<vector<char>>& grid) {
        queue<pair<int, int>> explore;
        explore.push(make_pair(i,j));
        grid[i][j] = '#';
        while (!explore.empty()) {
            pair<int,int> tmp = explore.front();
            explore.pop();
            if (tmp.first + 1 < grid.size() && grid[tmp.first+1][tmp.second] == '1') {
                explore.push(make_pair(tmp.first+1, tmp.second));
                grid[tmp.first+1][tmp.second] = '#';
            }
             if (tmp.second + 1 < grid[0].size() && grid[tmp.first][tmp.second+1] == '1') {
                explore.push(make_pair(tmp.first, tmp.second+1));
                grid[tmp.first][tmp.second+1] = '#';
            }
             if (tmp.first - 1 >= 0 && grid[tmp.first-1][tmp.second] == '1') {
                explore.push(make_pair(tmp.first-1, tmp.second));
                grid[tmp.first-1][tmp.second] = '#';
            }
             if (tmp.second- 1 >= 0 && grid[tmp.first][tmp.second-1] == '1') {
                explore.push(make_pair(tmp.first, tmp.second-1));
                grid[tmp.first][tmp.second-1] = '#';
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        //sanity check
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int rst = 0;
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                   SearchIsland(i, j, grid);
                   rst++;
                }
            }
        }
        return rst;
    }
};

通过这个题目BFS 和DFS做法的比较发现， 如果用DFS recursion的话，是不需要额外的数据结构和存储在数据结构里的数据形式的（eg: pair）， 而BFS除了需要用queue来存储数据，还是需要想想怎么存数据在queue里，对于二维矩阵，有时候可能是一对pair，有时候可能要存储object，所以这个问题也是BFS解决graph问题的一个点。DFS不需要想这么多，但是可能需要对DFS的树理解比较深，DFS和BFS还有一点不同是， DFS在expand的时候是不需要在那个时候把node mark 成visited的。。 

 注意与word search 那题采用DFS + mark visit II (backtracking) 来做的区别，以及解决问题类型的区别。 

class Solution {
private:
    bool SearchWord(int i, int j, vector<vector<char>>& board, string &word, int idx) {
        //base case
        if (board[i][j] == '#' || board[i][j] != word[idx]) return false; // no path to go
        if (idx == word.size()-1) return true;
        //mark
        char c = board[i][j];
        board[i][j] = '#';
        //expand
        if (i + 1 < board.size()) {
            if (SearchWord(i+1, j, board, word, idx+1)) return true;
        }
        if (i - 1>=0 ) {
            if (SearchWord(i-1, j, board, word, idx+1)) return true;
        }
        if (j+1 < board[0].size()) {
            if (SearchWord(i, j+1, board, word, idx+1)) return true;
        }
        if (j-1 >= 0) {
            if (SearchWord(i, j-1, board, word, idx+1)) return true;
        }
        board[i][j] = c;
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        //sanity check
        if (board.size() == 0 || board[0].size() == 0) return false;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++){
                if (board[i][j] == word[0]) {
                    if (SearchWord(i, j, board, word, 0)) return true;
                }
            }
        }
        return false;
    }
};