1020. Number of Enclaves
Leetcode Depth-first SearchGiven a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
Example 1:
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation:
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
Example 2:
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation:
All 1s are either on the boundary or can reach the boundary.
Note:
1 <= A.length <= 5001 <= A[i].length <= 5000 <= A[i][j] <= 1- All rows have the same size.
分析¶
类似于130. Surrounded Regions可以使用并查集做：
private int count; // 连接在一起的陆地数目
private int[] id; // id[i] = 陆地的序号为i
private int[] weight; // weight[i] = 陆地大小
public int numEnclaves(int[][] A) {
if (A == null || A.length == 0 || A[0].length == 0) return 0;
int n = A.length, m = A[0].length;
// 增加的虚拟边界的长度为p，q
int p = n + 2, q = m + 2;
// 初始化count
count = p*q;
// 初始化weight;
weight = new int[count];
for (int i = 0; i< count; i++)
weight[i] = 1;
// 初始化id
id = new int[count];
for (int i = 0; i < count; i++)
id[i] = i;
// 创建一个增加了虚拟边界的Enclave
int [][] B = new int [p][q];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
B[i + 1][j + 1] = A[i][j]; // 复制原来的数据
if (A[i][j] != 1) count--; // 陆地数量减小
}
}
for (int i = 0; i < p; i++) {
B[i][0] = 1; // 左边界
B[i][q-1] = 1; // 右边界
}
for (int j = 0; j < q; j++) {
B[0][j] = 1; // 上边界
B[p-1][j] = 1; // 下边界
}
System.out.println(Arrays.deepToString(B));
// 连接陆地
for (int i = 0; i < p; i++) {
for (int j = 0; j < q; j++) {
if (B[i][j] == 1) { // 是陆地
// 连接左边陆地
if (j > 1 && B[i][j-1] == 1)
union(i*q+j, i*q+j-1);
// 连接右边陆地
if (j + 1 < q && B[i][j+1] == 1)
union(i*q+j, i*q+j+1);
// 连接上边陆地
if (i - 1 > 0 && B[i-1][j] == 1)
union(i*q+j, (i-1)*q + j);
// 连接下边陆地
if (i + 1 < p && B[i+1][j] == 1)
union(i*q+j, (i+1)*q+j);
}
}
}
// 找寻未连接的陆地
int res = 0;
for (int i = 0; i < p; i++)
for (int j = 0; j < q; j++)
if (B[i][j] == 1 && !connected(0, i*q+j)) res++;
return res;
}
private boolean connected(int i, int j) {
return find(i) == find(j);
}
private int find(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
if (weight[i] > weight[j]) {
id[j] = i;
weight[i] += weight[j];
} else {
id[i] = j;
weight[j] += weight[i];
}
count--;
}
或者使用深度优先搜索
public int numEnclaves(int[][] A) {
if (A == null || A.length == 0 || A[0].length == 0) return 0;
int n = A.length, m = A[0].length;
int p = n + 2, q = m + 2;
boolean [][] visited = new boolean[p][q];
// B在A的基础上增加一个虚拟边界
int[][] B = new int[p][q];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
B[i+1][j+1] = A[i][j];
for (int i = 0; i < p; i++) {
B[i][0] = 1;
B[i][q-1] = 1;
}
for (int j = 0; j < q; j++) {
B[0][j] = 1;
B[p-1][j] = 1;
}
// dfs
dfs(B, visited, 0, 0);
// count
int count = 0;
for (int i = 0; i < p; i++)
for (int j = 0; j < q; j++)
if (B[i][j] == 1 && !visited[i][j]) count++;
return count;
}
private void dfs (int[][] B, boolean[][] visited, int i, int j) {
visited[i][j] = true;
if (i + 1 < B.length && B[i+1][j] == 1 && !visited[i+1][j])
dfs(B, visited, i+1, j);
if (i - 1 > 0 && B[i-1][j] == 1 && !visited[i-1][j])
dfs(B, visited, i-1, j);
if (j + 1 < B[0].length && B[i][j+1] == 1 && !visited[i][j+1])
dfs(B, visited, i, j+1);
if (j - 1 > 0 && B[i][j-1] == 1 && !visited[i][j-1])
dfs(B, visited, i, j-1);
}