numislands.cc

#include <stack>
#include <vector>
#include <iostream>
 
struct Index {
    int row; int col;
};
 
class Solution {
public:
    void dfs(
        std::vector<std::vector<char>>& grid, int rows, int cols, std::stack<Index>& stk
    )
    {
        while (!stk.empty()) {
            Index nodeIdx = stk.top();
            stk.pop();
 
            grid[nodeIdx.row][nodeIdx.col] = '2';
 
            if (nodeIdx.row + 1 < rows) {
                if (grid[nodeIdx.row + 1][nodeIdx.col] == '1') {
                    Index idx = {nodeIdx.row + 1, nodeIdx.col};
                    stk.push(idx);
                }
            }
 
            if (nodeIdx.row - 1 >= 0) {
                if (grid[nodeIdx.row - 1][nodeIdx.col] == '1') {
                    Index idx = {nodeIdx.row - 1, nodeIdx.col};
                    stk.push(idx);
                }
            }
 
            if (nodeIdx.col + 1 < cols) {
                if (grid[nodeIdx.row][nodeIdx.col + 1] == '1') {
                    Index idx = {nodeIdx.row, nodeIdx.col + 1};
                    stk.push(idx);
                }
            }
 
            if (nodeIdx.col - 1 >= 0) {
                if (grid[nodeIdx.row][nodeIdx.col - 1] == '1') {
                    Index idx = {nodeIdx.row, nodeIdx.col - 1};
                    stk.push(idx);
                }
            }
        }
    }
 
    int numIslands(std::vector<std::vector<char>>& grid) {
        std::stack<Index> stk;
        const int ROWS = grid.size();
        const int COLS = grid[0].size();
 
        int connectedComps = 0;
 
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (grid[i][j] == '1') {
                    // Initiate DFS, 1 -> 2
                    Index idx = {i, j};
                    stk.push(idx);
 
                    dfs(grid, ROWS, COLS, stk);
                    connectedComps++;
                }
            }
        }
        return connectedComps;
    }
};
 
int main() {
  std::vector<std::vector<char>> grid = {
    {'1','1','1','1','0'},
    {'1','1','0','1','0'},
    {'1','1','0','0','0'},
    {'0','0','0','0','0'}
  };
 
  Solution sol;
 
  int x = sol.numIslands(grid);
  std::cout << "CC --> " << x << "\n"; 
 
  return 0;
}