// 76 ms (Beats 9.9%)
// 22.53 MB (Beats 26.2%)
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        // This is equivalent to finding the number of connected components of a graph.
        // Each array element is a node.
        // grid[i][j] is connected to grid[p][q] iff they are horizontally/vertically adjacent and both contain "1".
        set<pair<int, int>> processed;
        stack<pair<int, int>> toSee; // timed out when this was a queue
        int numIslands = 0;

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1' && !processed.contains(pair{i, j})) {
                    toSee.emplace(pair{i, j});
                    
                    // Find all connected 1s.
                    while (toSee.size() != 0) {
                        const auto coord = toSee.top();
                        toSee.pop();
                        const int row = get<0>(coord);
                        const int col = get<1>(coord);
                        processed.emplace(pair{row, col});

                        if ((row - 1) >= 0 && grid[row-1][col] == '1' && !processed.contains(pair{row-1, col})) {
                            toSee.emplace(pair{row-1, col});
                        }
                        if ((col - 1) >= 0 && grid[row][col-1] == '1' && !processed.contains(pair{row, col-1})) {
                            toSee.emplace(pair{row, col-1});
                        }
                        if ((row + 1) < grid.size() && grid[row+1][col] == '1' && !processed.contains(pair{row+1, col})) {
                            toSee.emplace(pair{row+1, col});
                        }
                        if ((col + 1) < grid[0].size() && grid[row][col+1] == '1' && !processed.contains(pair{row, col+1})) {
                            toSee.emplace(pair{row, col+1});
                        }
                    }
                    numIslands++;
                }
            }
        }
        return numIslands;
    }
};