题目地址：

https://www.lintcode.com/problem/maximum-connected-area/description

给定一个二维$0-1$矩阵$A$，允许将其中的某一个$0$改为$1$，问能得到的最大的$1$连通块的面积（面积定义为$1$的个数）。

法1：并查集。遍历矩阵$A$，先将所有的$1$的位置做union，同时算出森林里每棵树的节点个数（也就是$1$连通块的$1$的个数）。接着再遍历一次$A$，关注那些值为$0$的位置，看一个四个方向的邻居的parent是多少（这里的parent指的是它们在并查集中的parent，当然四个邻居的parent有可能有$4$个，也有可能少于$4$个，因为也许有若干邻居是共享parent的），再将这些parent一个个取出来，算出它们所在树的size，再加上将$0$改为$1$多出来的$1$个单位的面积，这就是将当前$0$改为$1$之后，其所在的$1$连通块的面积，可以用此面积来更新答案。最后还需要注意一个问题，如果$A$里全是$1$，这时是找不到$0$的，则返回$A$的面积即可。代码如下：

import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class Solution { class UnionFind { int m, n; int[] parent, size; public UnionFind(int m, int n) { parent = new int[m * n]; for (int i = 0; i < m * n; i++) { parent[i] = i; } size = new int[m * n]; Arrays.fill(size, 1); this.m = m; this.n = n; } public void union(int x1, int y1, int x2, int y2) { union(transform(x1, y1), transform(x2, y2)); } public void union(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) { return; } parent[pa] = pb; size[pb] += size[pa]; } public int find(int x, int y) { return find(transform(x, y)); } public int find(int a) { if (parent[a] != a) { parent[a] = find(parent[a]); } return parent[a]; } public int getSize(int x, int y) { return size[transform(x, y)]; } public int getSize(int a) { return size[a]; } // 将二维坐标与一维坐标做映射 private int transform(int x, int y) { return x * n + y; } } /** * @param matrix: the matrix for calculation. * @return: return the max area after operation at most once. */ public int maxArea(int[][] matrix) { // write your code here. int m = matrix.length, n = matrix[0].length; UnionFind uf = new UnionFind(m, n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { int[] d = {1, 0, -1, 0, 1}; for (int k = 0; k < 4; k++) { int nextX = i + d[k], nextY = j + d[k + 1]; if (inBound(nextX, nextY, matrix) && matrix[nextX][nextY] == 1) { uf.union(i, j, nextX, nextY); } } } } } int res = 0; // 记录有没有找到0 boolean found = false; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { // 找到0了，标记一下 found = true; int[] d = {1, 0, -1, 0, 1}; // 存matrix[i][j]的四个邻居的parent，为了去重这里用哈希表 Set<Integer> set = new HashSet<>(); for (int k = 0; k < 4; k++) { int nextX = i + d[k], nextY = j + d[k + 1]; if (inBound(nextX, nextY, matrix) && matrix[nextX][nextY] == 1) { set.add(uf.find(nextX, nextY)); } } int curArea = 1; for (int num : set) { curArea += uf.getSize(num); } res = Math.max(res, curArea); } } } // 如果不存在0，则返回整个矩阵的面积 return found ? res : m * n; } private boolean inBound(int x, int y, int[][] matrix) { return 0 <= x && x < matrix.length && 0 <= y && y < matrix[0].length; } }

时间复杂度$O(mn{\log }^{\ast }(mn))$，空间$O(mn)$。

注解：这里的并查集用HashMap来写可能更精简一些，如果用二维映射到一维的方法的话，速度会快些，但写起来十分啰嗦。

法2：DFS + 标记连通块编号。为了统计面积的时候防止重复，我们可以对每个$1$连通块做编号。开一个二维数组$id$，使得$id[i][j]$是$A[i][j]$所在的$1$连通块的编号，具体方法是DFS的flood fill算法。同时在DFS的时候，还可以顺便算出某个编号对应的$1$连通块的面积，存入哈希表中。编号结束后，再对$A$进行遍历，遇到$0$的时候，就将其邻居的$1$所在的$1$连通块的面积加个总，然后更新答案。根据$id$数组就能避免重复统计。最后仍然要注意$A$里没有$0$的情况。代码如下：

import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class Solution { /** * @param matrix: the matrix for calculation. * @return: return the max area after operation at most once. */ public int maxArea(int[][] matrix) { // write your code here. int m = matrix.length, n = matrix[0].length; boolean[][] visited = new boolean[m][n]; int[][] id = new int[m][n]; int idx = 1; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j] && matrix[i][j] == 1) { map.put(idx, dfs(i, j, matrix, id, idx, visited)); idx++; } } } int res = 0; boolean found = false; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { found = true; Set<Integer> ids = new HashSet<>(); int[] d = {1, 0, -1, 0, 1}; int curArea = 1; for (int k = 0; k < 4; k++) { int nextX = i + d[k], nextY = j + d[k + 1]; if (inBound(nextX, nextY, matrix) && matrix[nextX][nextY] == 1) { int curId = id[nextX][nextY]; if (!ids.contains(curId)) { ids.add(curId); curArea += map.get(curId); } } } res = Math.max(res, curArea); } } } return found ? res : m * n; } // 将(x, y)所在的1连通块的所有位置在id数组里标记其编号为idx，同时返回该连通块面积 private int dfs(int x, int y, int[][] matrix, int[][] id, int idx, boolean[][] visited) { visited[x][y] = true; id[x][y] = idx; int[] d = {1, 0, -1, 0, 1}; int area = 1; for (int i = 0; i < 4; i++) { int nextX = x + d[i], nextY = y + d[i + 1]; if (inBound(nextX, nextY, matrix) && matrix[nextX][nextY] == 1 && !visited[nextX][nextY]) { area += dfs(nextX, nextY, matrix, id, idx, visited); } } return area; } private boolean inBound(int x, int y, int[][] matrix) { return 0 <= x && x < matrix.length && 0 <= y && y < matrix[0].length; } }

时空复杂度$O(mn)$。

注解：在上面并查集的方法里，事实上parent就扮演了这里的id的作用。