leetcode：827. 最大人工岛

题目来源

• leetcode

题目描述

题目解析

这道题是leetcode：695. 岛屿的最大面积的升级版。
现在我们有填海造陆的能力，可以把一个海洋各自变成陆地格子，进而让两块岛屿连城一块。

大致的思路我：我们先计算出所有岛屿的面积，在所有的格子上标记出岛屿的面积。然后搜索哪个海洋格子相邻的两个岛屿面积最大。例如下图中红色方框内的海洋格子，上边、左边都与岛屿相邻，我们可以计算出它变成陆地之后可以连接成的岛屿面积为 7+1+2=10。

然而，这个做法可能遇到一个问题。如下图中红色方框内的海洋格子，它的上边、如下图中红色方框内的海洋格子，它的上边、左边都与岛屿相邻，这时候连接成的岛屿面积难道是 7+1+77+1+7 ？显然不是。这两个 7 来自同一个岛屿，所以填海造陆之后得到的岛屿面积应该只有 7+1 = 87+1=8。

可以看到，要让算法正确，我们需要区分一个海洋格子相邻的两个7是否来自同一个岛屿。那么，我们不能在方框中标记岛屿的面积，而应该标记岛屿的索引（下标），另外用一个数组记录每个岛屿的面积，如下图所示。这样我们就可以发现红色方框内的海洋各自，它的「两个」相邻的岛屿实际上是同一个。

可以看到，这道题实际上是对网格做了两遍 DFS：第一遍 DFS 遍历陆地格子，计算每个岛屿的面积并标记岛屿；第二遍 DFS 遍历海洋格子，观察每个海洋格子相邻的陆地格子。

class Solution {bool inArea(vector<vector<int>>& grid, int row, int col) {return row >= 0 && col >= 0 && row <  grid.size() && col < grid[0].size();}/*** dfs方法，将格子填充为index，即表示这个格子属于哪个岛的* 计算岛屿面积，上下左右，当然这个可以优化的，因为不需要计算上面的，会有重复*/int dfs(vector<vector<int>>& grid, int row, int col, int index) {if(!inArea(grid, row, col)){return 0;}if(grid[row][col] != 1){    //不为1，表示为海洋格子或者已经遍历过了return 0;}grid[row][col] = index;  //设置当前格子为某个岛屿编号return (  1 + dfs(grid, row + 1, col, index)+ dfs(grid, row - 1, col, index)+ dfs(grid, row, col + 1, index)+ dfs(grid, row, col - 1, index));}/*** 对于海洋格子，找到上下左右* 每个方向，都要确保有效inArea以及是陆地格子，则表示是该海洋格子的陆地邻居*/set<int> findNeighbour(vector<vector<int>>& grid, int row, int col) {set<int> hashSet;if(inArea(grid, row+1, col) && grid[row+1][col] != 0) {hashSet.insert(grid[row+1][col]);}if(inArea(grid, row-1,col) && grid[row-1][col] != 0) {hashSet.insert(grid[row-1][col]);}if(inArea(grid, row, col+1) && grid[row][col+1] != 0) {hashSet.insert(grid[row][col+1]);}if(inArea(grid, row, col-1) && grid[row][col-1] != 0) {hashSet.insert(grid[row][col-1]);}return hashSet;}int largestIsland(vector<vector<int>>& grid) {if(grid.empty()){return 1;}int row = grid.size(), col = grid[0].size();int index = 2;   //index表示岛屿的编号，0是海洋1是陆地，从2开始遍历int max_area = 0;unordered_map<int, int> record;   //岛屿编号：岛屿面积/*** 计算每个岛屿的面积，并标记是第几个岛屿*/for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if(grid[i][j] == 1){   //遍历没有访问过的岛屿格子int size = dfs(grid, i, j, index);    //返回每个岛屿的面积，dfsrecord[index] = size;  //存入岛屿编号、岛屿面积max_area = std::max(max_area, size);    //记录最大的岛屿面积++index;   //岛屿编号增加}}}if(max_area == 0){ // 表示没有陆地，那么造一块，则返回1即可return 1;}/*** 遍历海洋格子，假设这个格子填充，那么就把上下左右是陆地的格子所在的岛屿连接起来*/for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if(grid[i][j] == 0){     //遍历海洋格子set<int> neighbors = findNeighbour(grid, i, j);  //把上下左右邻居放入set去重if(neighbors.empty()) {  //如果海洋格子周围没有格子不必计算continue;}std::set<int>::iterator  it = neighbors.begin();int area = 1;   //填充这个格子，初始为1，这个变量记录合并岛屿后的面积for (; it != neighbors.end() ; ++it) {area += record[*it];//该格子填充，则上下左右的陆地的都连接了，通过序号获得面积，加上面积}max_area = std::max(max_area, area);  //比较得到最大的面积}}}return max_area;}
};