题目:
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后,grid 中最大的岛屿面积是多少?
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1,最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1,岛屿的面积扩大为 4。
示例 3:
输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1,面积依然为 4。
提示:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/making-a-large-island
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
结果:
解题思路:
先通过dfs(深度优先)查找出每一个已有陆地。给每一个已有的陆地标号。并计算出每一个记号的陆地大小。然后循环空地,将四周陆地连接之后的面积最大者取出。
1、由于我们grid的标记是0和1组成,因此标号就从2开始。
2、当我们循环到grid [ i ] [ j ] 为1的时候,说明我们遇到了新大陆,于是gridNumIndex (大陆编号)+1,开始深度查找。
3、深度查找的时候要做两件事:1:将当前大陆标号,也就是在grid上将gridNum标上去;2:将当前大陆的面积计算出来。也就是又一个1 就加1.
4、最后遍历grid,当当前标号为0的时候计算上下左右四面有没有大陆,其大陆编号记录下来。并且对大陆编号去重。
5、将四周的大陆编号对应的面积相加再+1,就是当前这块地如果填平之后新大陆的面积。而我们只需要存储这个新大陆的最大值就好。
代码:
int getCount2Map(int **grid, int gridSize, int index, int colIndex, int griNum)
{
int count = 0;
// 往下查找
for (int i = index; i < gridSize; i++) {
if (grid[i][colIndex] != 1) {
break;
}
grid[i][colIndex] = griNum;
count++;
// 往右查找
for (int j = colIndex + 1; j < gridSize; j++) {
if (grid[i][j] != 1) {
break;
}
// 每个节点再次向四周查找
count += getCount2Map(grid, gridSize, i + 1, j, griNum);
grid[i][j] = griNum;
}
// 往左查找
for (int j = colIndex - 1; j >= 0; j--) {
if (grid[i][j] != 1) {
break;
}
// 每个节点再次向四周查找
count += getCount2Map(grid, gridSize, i + 1, j, griNum);
grid[i][j] = griNum;
}
}
// 往上查找
for (int i = index - 1; i >= 0; i--) {
if (grid[i][colIndex] != 1) {
break;
}
grid[i][colIndex] = griNum;
count++;
// 往右查找
for (int j = colIndex + 1; j < gridSize; j++) {
if (grid[i][j] != 1) {
break;
}
// 每个节点再次向四周查找
count += getCount2Map(grid, gridSize, i + 1, j, griNum);
grid[i][j] = griNum;
}
// 往左查找
for (int j = colIndex - 1; j >= 0; j--) {
if (grid[i][j] != 1) {
break;
}
// 每个节点再次向四周查找
count += getCount2Map(grid, gridSize, i + 1, j, griNum);
grid[i][j] = griNum;
}
}
return count;
}
int largestIsland(int** grid, int gridSize, int* gridColSize){
*gridColSize = 1;
int griNum[20000] = {0}; // 存储已有的每一个小岛面积
int griNumIndex = 1; // 存储已有小岛个数(为了和原有的0和1分开,从2开始计算。第一块小岛标记为2.
// 将连接的块注释为同一个岛屿号,同时记录该岛屿有多少块
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
if (grid[i][j] != 1) {
continue;
}
griNumIndex++;
griNum[griNumIndex] = getCount2Map(grid, gridSize, i, j, griNumIndex);
}
}
// 循环空地, 将连接后的最大数量计算
int max = 0;
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
if (grid[i][j] != 0) {
continue;
}
int upGriNum = i == 0 ? 0 : grid[i - 1][j];
int downGriNum = i == gridSize - 1 ? 0 : grid[i + 1][j];
int leftGriNum = j == 0 ? 0 : grid[i][j - 1];
int rightGriNum = j == gridSize - 1 ? 0 : grid[i][j + 1];
if (downGriNum == upGriNum) {
downGriNum = 0;
}
if (leftGriNum == upGriNum || leftGriNum == downGriNum) {
leftGriNum = 0;
}
if (rightGriNum == upGriNum || rightGriNum == leftGriNum || rightGriNum == downGriNum) {
rightGriNum = 0;
}
int count = griNum[upGriNum] + griNum[downGriNum] + griNum[leftGriNum] + griNum[rightGriNum] + 1;
max = max >= count ? max : count;
}
}
if (max == 0) {
return gridSize * gridSize;
}
return max;
}