大部分都是模板题，以训练理解原理为主。

一、网格类

130. 被围绕的区域

题解

class Solution {
public:
    int M, N;
    void solve(vector<vector<char>> &board) {
        if (board.size() == 0)return;
        M = board.size();
        N = board[0].size();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                bool isEdge = (i == 0 || j == 0 || i == M - 1 || j == N - 1);
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    void dfs(vector<vector<char>> &board, int i, int j) {
        if (i < 0 || j < 0 || i >= M || j >= N || board[i][j] == 'X' || board[i][j] == '#') { return; }
        board[i][j] = '#';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
};

200. 岛屿数量

class Solution {
public:
    vector<vector<int>> dirs = {
            {0,  1},
            {1,  0},
            {0,  -1},
            {-1, 0}
    };
    vector<vector<bool>> visited;
    int M, N;
    int numIslands(vector<vector<char>> &grid) {
        M = grid.size();
        N = grid[0].size();
        visited = vector<vector<bool>>(M, vector<bool>(N, 0));
        int ans = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ans += 1;
                }
            }
        }
        return ans;
    }
    void dfs(vector<vector<char>> &grid, int i, int j) {
        //染色
        visited[i][j] = 1;
        for (auto dir:dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (isValid(x, y) && !visited[x][y] && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }
    bool isValid(int i, int j) {
        if (i < 0 || i >= M || j < 0 || j >= N) {
            return false;
        }
        return true;
    }
};

695. 岛屿的最大面积

class Solution {
public:
    vector<vector<int>> dirs = {
            {0,  1},
            {1,  0},
            {0,  -1},
            {-1, 0}
    };
    vector<vector<bool>> visited;
    int M, N;
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        M = grid.size();
        N = grid[0].size();
        int ans = 0;
        visited = vector<vector<bool>>(M, vector<bool>(N, 0));
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && grid[i][j]) {
                    ans = max(ans, dfs(grid, i, j));
                }
            }
        }
        return ans;
    }
    int dfs(vector<vector<int>> &grid, int i, int j) {
        visited[i][j] = 1;
        int ans = 1;
        for (auto dir:dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (isValid(x, y) && !visited[x][y] && grid[x][y]) {
                ans += dfs(grid, x, y);
            }
        }
        return ans;
    }
    bool isValid(int i, int j) {
        return i >= 0 && i < M && j >= 0 && j < N;
    }
};

面试题 16.19. 水域大小

DFS解法：

class Solution {
public:
    int M, N;
    vector<vector<bool>> visited;
    vector<vector<int>> dirs = {{0,  1},
                                {1,  1},
                                {1,  0},
                                {1,  -1},
                                {0,  -1},
                                {-1, -1},
                                {-1, 0},
                                {-1, 1}};
    vector<int> ans;
    vector<int> pondSizes(vector<vector<int>> &land) {
        M = land.size();
        N = land[0].size();
        visited = vector<vector<bool>>(M, vector<bool>(N, false));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (!visited[i][j] && land[i][j] == 0) {
                    ans.push_back(dfs(land, i, j));
                }
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
    int dfs(vector<vector<int>> &land, int i, int j) {
        if (i < 0 || i >= M || j < 0 || j >= N || land[i][j] || visited[i][j]) {
            return 0;
        }
        visited[i][j] = 1;
        int res = 1;
        for (int k = 0; k < dirs.size(); k++) {
            int x = i + dirs[k][0];
            int y = j + dirs[k][1];
            res += dfs(land, x, y);
        }
        return res;
    }
};

BFS解法：

class Solution {
public:
    vector<vector<bool>> visited;
    vector<int> ans;
    vector<vector<int>> dirs = {
            {1,  0},
            {1,  -1},
            {0,  -1},
            {-1, -1},
            {-1, 0},
            {-1, 1},
            {0,  1},
            {1,  1}
    };
    int M, N;
    vector<int> pondSizes(vector<vector<int>> &land) {
        M = land.size();
        N = land[0].size();
        queue<pair<int, int>> q;
        int count = 0;
        visited = vector<vector<bool>>(M, vector<bool>(N, 0));
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; ++j) {
                if (visited[i][j] || land[i][j] > 0) {
                    continue;
                }
                q.push({i, j});
                visited[i][j] = 1;
                count = 0;
                while (!q.empty()) {
                    pair<int, int> p = q.front();
                    count += 1;
                    q.pop();
                    for (int k = 0; k < dirs.size(); k++) {
                        int x = p.first + dirs[k][0];
                        int y = p.second + dirs[k][1];
                        if (x < 0 || x >= M || y < 0 || y >= N || visited[x][y] || land[x][y] > 0) {
                            continue;
                        }
                        visited[x][y] = 1;
                        q.push({x, y});
                    }
                }
                ans.push_back(count);
            }
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};