200.岛屿数量

两天宇宙人

2020-02-16

🥩stack

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        stack<pair<int, int> > stk;
        set<pair<int, int> > rd;
        int tl = 0;
        for(int i = 0; i < grid.size(); ++i)
            for(int j = 0; j < grid[i].size(); ++j)
            {
                if(grid[i][j] == '1' && !rd.count({i, j})) {
                    
                    ++tl;
                    // cout << tl << endl;
                    // cout << i << " " << j << endl;
                    stk.push({i , j});
                    rd.insert({i, j});
                    while(stk.size()) {
                        auto p = stk.top();
                        stk.pop();
                        int i = p.first;
                        int j = p.second;
                        grid[i][j] == '0';
                        if(i + 1 < grid.size() && grid[i + 1][j] == '1' && !rd.count({i + 1, j}))
                        {
                            // cout << i + 1<< " " << j <<endl;
                            stk.push({i + 1, j});
                            rd.insert({i + 1, j});
                        }
                        if(j + 1 < grid[i].size() && grid[i][j + 1] == '1' && !rd.count({i, j + 1}))
                        {
                            // cout << i << " " << j + 1<<endl;
                            stk.push({i , j + 1});
                            rd.insert({i, j + 1});
                        }
                        if(j - 1 >= 0 && grid[i ][j - 1] == '1' && !rd.count({i, j - 1}))
                        {
                            // cout << i << " " << j - 1<<endl;
                            stk.push({i , j - 1});
                            rd.insert({i, j - 1});
                        }
                        if(i - 1 >= 0 && grid[i - 1][j ] == '1' && !rd.count({i - 1, j }))
                        {
                            // cout << i << " " << j - 1<<endl;
                            stk.push({i -1, j });
                            rd.insert({i - 1, j });
                        }
                    }
                }
            }
        return tl;
    }
};