Given an N×N grid representing a maritime region where ‘.’ denotes ocean and ‘#’ denotes land, determine how many islands will be completely submerged due to rising sea levels.

An island consists of connected land cells in four directions (up, down, left, right). Each land cell adjacent to ocean will be submerged. The task is to count how many islands have all they land cells bordered by ocean.

The algorithm uses breadth-first search (BFS) to traveres each island. For every unvisited land cell, a BFS is initiated to explore the entire island. During traversal, we track:

1. Total number of land cells in the island (total).
2. Number of land cells that border ocean (bound).

If total equals bound, it indicates that the entire island is surrounded by ocean and thus will be fully submerged.

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n;
char grid[N][N];
bool visited[N][N];
PII queue[N * N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int startX, int startY, int &total, int &boundary) {
    int head = 0, tail = 0;
    queue[0] = {startX, startY};
    visited[startX][startY] = true;

    while (head <= tail) {
        PII current = queue[head++];
        total++;

        bool isEdge = false;

        for (int i = 0; i < 4; i++) {
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];

            if (newX < 0 || newX >= n || newY < 0 || newY >= n) continue;

            if (visited[newX][newY]) continue;

            if (grid[newX][newY] == '.') {
                isEdge = true;
                continue;
            }

            queue[++tail] = {newX, newY};
            visited[newX][newY] = true;
        }

        if (isEdge) boundary++;
    }
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%s", grid[i]);

    int result = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && grid[i][j] == '#') {
                int totalCells = 0, edgeCells = 0;
                bfs(i, j, totalCells, edgeCells);
                if (totalCells == edgeCells) result++;
            }
        }
    }

    printf("%d\n", result);
    return 0;
}