题解 | #岛屿数量#

#include <utility>
class Solution {
  public:
    int solve(vector<vector<char> >& grid) {
        set<pair<int, int>> recxy; // 用于记录被搜索到的坐标
        int res = 0;
        for (int j = 0; j < grid.size(); j++) {// y
            for (int i = 0; i < grid[0].size(); i++) { // x
                if (!hasRec(recxy, i, j) && grid[j][i] == '1') {
                    dfs(grid, i, j, recxy);
                    res++;
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<char> >& grid, int x, int y,
             set<pair<int, int>>& recxy) { //深度优先搜索
        vector<pair<int, int>> xystack;
        pair<int, int> xy(x, y), tmp;
        xystack.push_back(xy);
        recxy.insert(xy);
        int xtmp, ytmp;
        while (!xystack.empty()) {
            xy = xystack.back();
            xtmp = xy.first;
            ytmp = xy.second;
            if (valid(grid, xtmp - 1, ytmp) && !hasRec(recxy, xtmp - 1, ytmp) &&
                    grid[ytmp][xtmp - 1] == '1') {
                tmp.first = xtmp - 1;
                tmp.second = ytmp;
                xystack.push_back(tmp);
                recxy.insert(tmp);
                continue;
            }
            if (valid(grid, xtmp, ytmp - 1) && !hasRec(recxy, xtmp, ytmp - 1) &&
                    grid[ytmp - 1][xtmp] == '1') {
                tmp.first = xtmp;
                tmp.second = ytmp - 1;
                xystack.push_back(tmp);
                recxy.insert(tmp);
                continue;
            }
            if (valid(grid, xtmp + 1, ytmp) && !hasRec(recxy, xtmp + 1, ytmp) &&
                    grid[ytmp][xtmp + 1] == '1') {
                tmp.first = xtmp + 1;
                tmp.second = ytmp;
                xystack.push_back(tmp);
                recxy.insert(tmp);
                continue;
            }
            if (valid(grid, xtmp, ytmp + 1) && !hasRec(recxy, xtmp, ytmp + 1) &&
                    grid[ytmp + 1][xtmp] == '1') {
                tmp.first = xtmp;
                tmp.second = ytmp + 1;
                xystack.push_back(tmp);
                recxy.insert(tmp);
                continue;
            }
            xystack.pop_back();
        }
    }
    bool hasRec(set<pair<int, int>>& recxy, int x, int y) { //判断是否被记录
        pair<int, int> xy(x, y);
        return recxy.find(xy) != recxy.end();
    }
    bool valid(vector<vector<char> >& grid, int x, int y) { //判断坐标是否超出矩阵尺寸
        return x >= 0 && y >= 0 && x < grid[0].size() && y < grid.size();
    }

};