#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// I use this Point struct rather than a pair<int, int> to make it shortes
// Point rather than pair<int, int> to initialize
// Point.x and Point.y rather than Point.first and Point.second
struct Point {
    int x;
    int y;
    Point (int x, int y): x(x), y(y) {}
};

// This function is to check if a Point's coordinates are within the map
bool InMap(const vector<vector<int>>& map, const Point& current) {

    return (current.x >= 0 && current.x < map.size() && current.y >= 0 && current.y < map[0].size());
}

// This function returns the number of connected elements to {0,0} equal to 1 within map
int NumElem(const vector<vector<int>>& map) {

    int ans = 0;

    vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));

    vector<Point> neighbors_map = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    queue<Point> qPoints;
    qPoints.push({0, 0});
    visited_map[0][0] = true;

    while (!qPoints.empty()) {
        Point current = qPoints.front();
        qPoints.pop();
        ++ans;

        for (int i = 0; i < 4; ++i) {
            Point neighbor({current.x + neighbors_map[i].x, current.y + neighbors_map[i].y});
            if (InMap(map, neighbor) && map[neighbor.x][neighbor.y] == 1 && !visited_map[neighbor.x][neighbor.y]) {
                visited_map[neighbor.x][neighbor.y] = true;
                qPoints.push(neighbor);
            }
        }
    }

    return ans;
}

// This function sets visited_map to true for the elements connected to start within map
void FloodFill(const vector<vector<int>>& map, vector<vector<bool>>& visited_map, const Point& start) {

    vector<Point> neighbors_map = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    queue<Point> qPoints;
    qPoints.push({start.x, start.y});
    visited_map[start.x][start.y] = true;

    int val = map[start.x][start.y];

    while (!qPoints.empty()) {
        Point current = qPoints.front();
        qPoints.pop();

        for (int i = 0; i < 4; ++i) {
            Point neighbor({current.x + neighbors_map[i].x, current.y + neighbors_map[i].y});
            if (InMap(map, neighbor) && map[neighbor.x][neighbor.y] == val && !visited_map[neighbor.x][neighbor.y]) {
                visited_map[neighbor.x][neighbor.y] = true;
                qPoints.push(neighbor);
            }
        }
    }
}

// This function returns the number of islands within map
// Problem when one island has a lake that has islands
// These islands are counted. However they should not
/*
int NumIslands(const vector<vector<int>>& map) {

    vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));
    int ans = 0;

    for (int i = 0; i < map.size(); ++i) {
        for (int j = 0; j < map[0].size(); ++j) {
            if (map[i][j] == 1 && visited_map[i][j] == false) {
                Point current(i,j);
                FloodFill(map, visited_map, current);
                ++ans;
            }
        }
    }

    return ans;
}
*/
// This function returns the number of islands within map
// It does not count the lake's islands
int NumIslands(const vector<vector<int>>& map) {

    vector<Point> neighbors_map = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));
    FloodFill(map, visited_map, {0,0});
    int ans = 0;

    for (int i = 0; i < map.size(); ++i) {
        for (int j = 0; j < map[0].size(); ++j) {
            bool neighbor_is_sea = false;
            int k = 0;
            while (!neighbor_is_sea && k < 4) {
                Point neighbor({i + neighbors_map[k++].x, j + neighbors_map[k++].y});
                neighbor_is_sea = InMap(map, neighbor) && visited_map[neighbor.x][neighbor.y];
            }

            if (neighbor_is_sea && map[i][j] == 1 && !visited_map[i][j]) {
                Point current(i,j);
                FloodFill(map, visited_map, current);
                ++ans;
            }
        }
    }

    return ans;
}

int main()
{
    vector<vector<int>> map1 = {{0, 0, 0, 0, 0, 0},
                            {0, 1, 1, 0, 1, 0},
                            {0, 1, 1, 0, 1, 0},
                            {0, 0, 0, 0, 0, 0},
                            {0, 0, 0, 0, 1, 0}};

    vector<vector<int>> map2 = {{0, 0, 0, 0, 0, 0, 0},
                            {0, 1, 1, 1, 1, 1, 0},
                            {0, 1, 0, 0, 0, 1, 0},
                            {0, 1, 0, 1, 0, 1, 0},
                            {0, 1, 0, 0, 0, 1, 0},
                            {0, 1, 1, 1, 1, 1, 0},
                            {0, 0, 0, 0, 0, 0, 0}};

    std::cout << NumIslands(map1) << std::endl;
    std::cout << NumIslands(map2) << std::endl;
    return 0;
}