#include <iostream>
#include <vector>

class Solution {
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        int numIslands = 0;
        int rows = grid.size();
        if (rows == 0) {
            return numIslands;
        }
        int cols = grid[0].size();

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }

        return numIslands;
    }

private:
    void dfs(std::vector<std::vector<char>>& grid, int row, int col, int rows, int cols) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0';  // Mark as visited

        // Explore adjacent cells in all four directions
        dfs(grid, row - 1, col, rows, cols); // Up
        dfs(grid, row + 1, col, rows, cols); // Down
        dfs(grid, row, col - 1, rows, cols); // Left
        dfs(grid, row, col + 1, rows, cols); // Right
    }
};

int main() {
    std::vector<std::vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    Solution solution;
    int islands = solution.numIslands(grid);
    std::cout << "Number of islands: " << islands << std::endl;

    return 0;
}