岛屿问题模板C++

岛屿问题模板C++"/>

岛屿问题模板C++

题目列表

• • leetcode 200. 岛屿数量
  • leetcode 463 岛屿的周长
  • leetcode 695. 岛屿的最大面积
  • leetcode 934.最短的桥
  • leetcode 1254. 统计封闭岛屿的数目
  • leetcode 827. 最大人工岛

leetcode 200. 岛屿数量

题目
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。
实例

输入:
11110
11010
11000
00000
输出: 1

代码

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int count = 0;if(grid.size()==0||grid[0].size()==0) return count;for(int x = 0; x < grid.size(); x++){for(int y = 0; y < grid[0].size(); y++){if(grid[x][y] == '1'){dfs(grid, x, y);count++;}}}return count;}void dfs(vector<vector<char>> & grid, int x, int y){if(x < 0 || y < 0|| x >= grid.size()|| y >= grid[0].size()) return;else if(grid[x][y] == '1'){grid[x][y] = '0';dfs(grid, x-1,y);dfs(grid, x+1, y);dfs(grid, x, y+1);dfs(grid,x, y-1);}}};

注：判断数组是否越界原来写了一个函数调用，可是超时了，所以加到了DFS函数，AC。

leetcode 463 岛屿的周长

题目
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。

网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

实例

输入:
[[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出: 16

代码

class Solution {
public:int islandPerimeter(vector<vector<int>>& grid) {//题目给出其中恰有一个岛屿，没有判断o边界for(int x = 0; x