Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Number of Enclaves

Medium · Graphs · Asked at Amazon, Google, Microsoft

The grid has land (1) and sea (0). A move goes from a land cell to an adjacent land cell (up/down/left/right) or walks off the grid from a border cell. Print the number of land cells from which you cannot walk off the grid.

Input

First line: r c. Next r lines: c values (0 or 1).

Output

The number of enclosed land cells.

Constraints

Flood-fill from every border land cell; the land cells left unvisited are the answer.

Example 1

Input

4 4
0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0

Output

3

Example 2

Input

4 4
0 1 1 0
0 0 1 0
0 0 1 0
0 0 0 0

Output

0

Hints

  1. Land connected to a border land cell can walk off the grid.
  2. Flood-fill from all border land cells; count the land cells that were never reached.

Approach

Multi-source BFS from every land cell on the border, marking reachable land (set it to 2). Every cell still equal to 1 afterwards is enclosed, so count them. Same trick as Surrounded Regions: search from the outside in.

Complexity: O(r · c) time · O(r · c) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int R, C;
    cin >> R >> C;
    vector<vector<int>> g(R, vector<int>(C));
    for (auto &row : g)
        for (auto &x : row) cin >> x;
    queue<pair<int, int>> q;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if ((i == 0 || j == 0 || i == R - 1 || j == C - 1) && g[i][j] == 1) g[i][j] = 2, q.push({i, j});
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int a = x + dx[k], b = y + dy[k];
            if (a >= 0 && b >= 0 && a < R && b < C && g[a][b] == 1) g[a][b] = 2, q.push({a, b});
        }
    }
    int count = 0;
    for (auto &row : g)
        for (int x : row) count += x == 1;
    cout << count << "\n";
    return 0;
}

Python solution

import sys
from collections import deque

data = list(map(int, sys.stdin.read().split()))
R, C = data[0], data[1]
g = [data[2 + i * C : 2 + (i + 1) * C] for i in range(R)]
q = deque()
for i in range(R):
    for j in range(C):
        if (i in (0, R - 1) or j in (0, C - 1)) and g[i][j] == 1:
            g[i][j] = 2
            q.append((i, j))
while q:
    x, y = q.popleft()
    for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
        if 0 <= a < R and 0 <= b < C and g[a][b] == 1:
            g[a][b] = 2
            q.append((a, b))
print(sum(row.count(1) for row in g))

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int R = (int) in.nval;
        in.nextToken();
        int C = (int) in.nval;
        int[][] g = new int[R][C];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++) {
                in.nextToken();
                g[i][j] = (int) in.nval;
                if ((i == 0 || j == 0 || i == R - 1 || j == C - 1) && g[i][j] == 1) {
                    g[i][j] = 2;
                    q.add(new int[] {i, j});
                }
            }
        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int k = 0; k < 4; k++) {
                int a = p[0] + dx[k], b = p[1] + dy[k];
                if (a >= 0 && b >= 0 && a < R && b < C && g[a][b] == 1) {
                    g[a][b] = 2;
                    q.add(new int[] {a, b});
                }
            }
        }
        int count = 0;
        for (int[] row : g)
            for (int x : row) if (x == 1) count++;
        System.out.println(count);
    }
}

Solve Number of Enclaves online · All practice problems