200. Number of Islands

做题历程：

1. 2016/Oct/20，本题应该做了不止1次，本次大概耗时7分钟，独立解出

本题难度算是比较简单的，尤其是做过一次，大体思路就是：

• 以DFS为框架，遍历所有点
• 要将所有为1的点标记为2，这样就会把跟我们测的1所有可以触及的点都会标记到
• 这样再遇到为1的点，这就肯定是一个新岛。。这题的核心就在于：标记 + DFS

代码如下：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        if (grid.empty() || grid[0].empty()) {
            return cnt;
        }
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    ++cnt;
                    mark(i, j, grid);
                }
            }
        }
        return cnt;
    }

    void mark(int i, int j, vector<vector<char>>& grid) {
        grid[i][j] = '2';
        if (i > 0 && grid[i-1][j] == '1') {
            mark(i - 1, j, grid);
        }
        if (i < grid.size() - 1 && grid[i+1][j] == '1') {
            mark(i + 1, j, grid);
        }
        if (j > 0 && grid[i][j-1] == '1') {
            mark(i, j - 1, grid);
        }
        if (j < grid[0].size() && grid[i][j+1] == '1') {
            mark(i, j + 1, grid);
        }
    }
};