天池在线编程 2020国庆八天乐 - 4. 生成更大的陆地（BFS）

文章目录

• • 1. 题目
  • 2. 解题

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. 解题

class Solution { public:/*** @param grid: * @return: nothing*/int n, color = 2, maxarea = 0;unordered_map<int, int> m;// color, areavector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};int largestIsland(vector<vector<int>> &grid) {// write your code heren = 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);} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的天池在线编程 2020国庆八天乐 - 4. 生成更大的陆地（BFS）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。