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
- 1 ≤ r, c ≤ 500
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
- Land connected to a border land cell can walk off the grid.
- 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);
}
}