1. 题目
https://tianchi.aliyun.com/oj/118289365933779217/122647324262601668
LeetCode 上也有该题 827. 最大人工岛
描述 在一个0和1的2D网格中，我们最多将一个0改为1。 之后，最大岛屿的大小是多少？ （一个岛是四个方向上互相连接的一组1）。
示例
样例 1:
输入：[[1,0]，[0,1]]
输出：3
解释：
将0改为1并连接两个1，然后我们得到一个面积= 3的岛。
样例 2：
输入：[[1,1]，[1,0]]
输出：4
解释：
将0更改为1并使岛变大，只有一个面积= 4的岛。
样例 3:
输入：[[1,1]，[1,1]]
输出：4
解释：
不能将任何0更改为1，只有一个面积= 4的岛。2. 解题
代码语言：javascript复制class Solution {
public:
/**
* @param grid:
* @return: nothing
*/
int n, color = 2, maxarea = 0;
unordered_map<int, int> m;// color, area
vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
int largestIsland(vector<vector<int>> &grid) {
// write your code here
n = grid.size();
for(int i = 0, j; i < n; i)
{
for(j = 0; j < n; j)
{
if(grid[i][j]==1)
{
color ;
bfs(grid, i, j, color);
}
}
}
for(int i = 0, j; i < n; i)
{
for(j = 0; j < n; j)
{
if(grid[i][j] == 0)
{
unordered_set<int> s;//记录四周的颜色有几种
int area = 1;
for(int k = 0; k < 4; k)
{
int x = i dir[k][0];
int y = j dir[k][1];
if(x>=0 && x < n && y>=0 && y < n && !s.count(grid[x][y]))
{
s.insert(grid[x][y]);//插入颜色
area = m[grid[x][y]];//加入这种颜色的陆地面积
}
}
maxarea = max(maxarea, area);
}
}
}
return maxarea;
}
void bfs(vector<vector<int>> &grid, int i, int j, int color)
{
int area = 0, x, y;
queue<pair<int, int>> q;
q.push({i,j});
grid[i][j] = color;
while(!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
area ;
for(int k = 0; k < 4; k)
{
i = x dir[k][0];
j = y dir[k][1];
if(i >= 0 && i < n && j >= 0 && j < n && grid[i][j]==1)
{
q.push({i, j});
grid[i][j] = color;
}
}
}
m[color] = area;//记录这个颜色的陆地的面积
maxarea = max(maxarea, area);
}
}; 
