C练题笔记之：Leetcode-827. 最大人工岛

题目：

给你一个大小为 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;
}