题目描述
在二维地图上， 0 代表海洋， 1 代表陆地，我们最多只能将一格 0 海洋变成 1 变成陆地。
进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）
示例1
输入： [[1, 0], [0, 1]] 输出： 3 解释： 将一格 0 变成 1 ，最终连通两个小岛得到面积为 3 的岛屿。
示例2
输入： [[1, 1], [1, 0]] 输出： 4 解释： 将一格 0 变成 1 ，岛屿的面积扩大为 4 。
示例3
输入： [[1, 1], [1, 1]] 输出： 4 解释： 没有 0 可以让我们变成 1 ，面积依然为 4 。
提示
- 1 <= grid.length = grid[0].length <= 50
- 0 <= grid[i][j] <= 1
题解
没有做过这种类型题目的强烈建议自己动手实现一遍，对提升代码能力有很大帮助。
这题虽然是 hard 难度，但其实没有什么算法，只用到了 dfs 求连通块而已。我们只需要知道填充了一个 0 之后，它上下左右跟它相邻的 4 块连通块是多大。
首先普及一下什么是连通块，就是一块由 1 组成的区域，其中任意两块 1 都可以由一条 1 组成的路径走过去（只能上下左右走）。那么这题我们遍历所有的 0 ，把它四周的连通块大小加起来就是填充了这块 0 之后的连通块大小了。那么问题是怎么知道它周围连通块的大小呢？
首先我们得求出所有连通块的大小，然后存下来，这就得用到 dfs 了。
用二维数组 index （初始化为 -1）记录方块是否被搜索过。然后遍历所有的方块，如果是 1 ，并且 index 为 -1 （也就是没被搜索过），那么它的 index 设为 1 ，表示被搜索过了。然后从它开始向四周进行 dfs ，直到跟它相连的所有 1 的连通块都被搜索完毕。这时候整块连通块里面的 1 方块的 index 都被设成了 1 ，就算以后被遍历到了也不会被搜索了。那么大小怎么记录呢？只需要设置一个变量 cnt 初始为 1 ，然后 dfs 的时候遇到一个未被搜索的块就加 1 ，最后 cnt 就是当前连通块的大小了。
光知道了每个连通块的大小还不行，对于一个 0 块，四周的 1 方块万一属于同一个连通块怎么办？得区分它们，不然就会被重复计算。所以在上面的 dfs 之前，给那块连通块一个唯一的编号（从 0 开始），遇到下一个连通块就加 1 。这样 index 数组就可以用来存连通块的编号了，同时还能表示方块是否被搜索过。
具体的细节还得看代码，有很多实现的技巧，当然我写的还有一些优化余地。
代码
c++
class Solution { public: static const int N = 55; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int index[N][N], area[N*N], flag[N*N]; int m, n; int largestIsland(vector<vector<int>>& grid) { m = grid.size(); n = grid[0].size(); memset(index, -1, sizeof index); memset(area, 0, sizeof area); memset(flag, 0, sizeof flag); int res = 0, idx = -1; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1 && index[i][j] == -1) { int cnt = 1; index[i][j] = ++idx; dfs(i, j, idx, cnt, grid); area[idx] = cnt; res = max(res, cnt); } } } for (int x = 0; x < m; ++x) { for (int y = 0; y < n; ++y) { if (grid[x][y] == 0) { int tmp = 1; for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (inside(nx, ny) && grid[nx][ny] == 1 && !flag[index[nx][ny]]) { flag[index[nx][ny]] = 1; tmp += area[index[nx][ny]]; } } for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (inside(nx, ny) && grid[nx][ny] == 1 && flag[index[nx][ny]]) { flag[index[nx][ny]] = 0; } } res = max(res, tmp); } } } return res; } bool inside(int x, int y) { return 0 <= x && x < m && 0 <= y && y < n; } void dfs(int x, int y, int idx, int& cnt, vector<vector<int>>& grid) { for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (inside(nx, ny) && grid[nx][ny] == 1 && index[nx][ny] == -1) { index[nx][ny] = idx; dfs(nx, ny, idx, ++cnt, grid); } } } };
后记
dfs 求连通块是常规操作，必须要学会，很考验代码功底，要细心，不然很容易写错。
