目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：力扣

描述：

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

示例 3：

输入：grid = [[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]
输出：2

提示：

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

 

解题思路：

/*** 1254. 统计封闭岛屿的数目* 解题思路：* 标记状态，0代表没有遍历，1代表海域，2代表遍历中，3代表是不是独立岛屿，4代表是独立岛屿。* 然后遍历grid，如果grid[i][j]==0，则查找从这个点触发所有能达到的区域，并记录。返回值是是否是独立岛屿，* 如果是则把所有达到的点改为4，并且数量+1，否则改为3。* 然后继续查找下一个不为0的点。*/

代码：

class Solution {
public:vector<vector<int>> directions = {{1, 0},{0, 1},{-1, 0},{0, -1},};const int STATE_NO_TRAVEL = 0;       // 没有遍历const int STATE_SEA = 1;             // 海域const int STATE_SEARCHING = 2;       // 遍历中const int STATE_NO_CLOSE_ISLAND = 3; // 确定不是独立岛屿const int STATE_CLOSE_ISLAND = 4;    // 确定是独立岛屿bool searchClosedIsland(vector<vector<int>> &grid, bool parentFlag, int x, int y, vector<vector<int>> &record){if (y == 0 || y == grid.size() - 1 || x == 0 || x == grid[0].size() - 1){record.push_back({y, x});return false;}record.push_back({y, x});bool flag = true;for (int i = 0; i < directions.size(); i++){int newX = x + directions[i][1];int newY = y + directions[i][0];// 为3代表正在遍历中if (grid[newY][newX] == STATE_SEARCHING){continue;}// 为1代表遇到海水if (grid[newY][newX] == STATE_SEA){continue;}// 为2代表遇到未封闭的岛屿if (grid[newY][newX] == STATE_NO_CLOSE_ISLAND){flag = false;continue;}// 为0代表未遍历过if (grid[newY][newX] != 0){cout << "error" << endl;}grid[newY][newX] = STATE_SEARCHING;flag = flag & searchClosedIsland(grid, flag, newX, newY, record);}return flag & parentFlag;}int closedIsland(vector<vector<int>> &grid){int sum = 0;vector<vector<int>> record;for (int y = 0; y < grid.size(); y++){for (int x = 0; x < grid[0].size(); x++){if (grid[y][x] != 0){continue;}bool flag = searchClosedIsland(grid, true, x, y, record);if (flag){sum++;}for (auto it : record){// cout << it[0] << " ";grid[it[0]][it[1]] = flag ? STATE_CLOSE_ISLAND : STATE_NO_CLOSE_ISLAND;}record.clear();}}return sum;}
};