目录链接:
力扣编程题-解法汇总_分享+记录-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;}
};