【剑斩OFFER】算法的暴力美学——LeetCode 200 题：岛屿数量

一、题目描述

二、算法原理

思路：使用 BFS 算法

这道题目是基于：https://blog.csdn.net/2403_84958571/article/details/157102131?spm=1011.2415.3001.10575&sharefrom=mp_manage_link

图形化渲染的题目来的，因为图形化显然遍历上下左右时，将遍历的值修改了，所以不会重复遍历，所以：我们只要补充一下这道题：我们也弄出一个二维数组，大小跟题目给的一样，但是这里面存储的值为：bool 值，我们初始化时将他初始化为 fasle，代表未查找过的岛屿，如果我们使用 BFS 算法查找时，要将遍历过的值变成：true ，代表查找过了；

三、代码实现

class Solution { int dy[4] = {0,0,1,-1}; int dx[4] = {1,-1,0,0}; typedef pair<int,int> PII; void checkgrid(queue<PII>& que,vector<vector<bool>>& tmp,vector<vector<char>>& grid) { while(que.size())//BFS 算法 { auto [x,y] = que.front(); que.pop(); tmp[x][y] = true; for(int i = 0; i < 4; i++) { int a = x + dy[i]; int b = y + dx[i]; if(a >= 0 && a < tmp.size() && b >= 0 && b < tmp[0].size() && grid[a][b] == '1' && tmp[a][b] == false) { tmp[a][b] = true; que.push({a,b}); } } } } public: int numIslands(vector<vector<char>>& grid) { vector<vector<bool>> tmp(grid.size(),vector<bool>(grid[0].size(),false));//模拟遍历过的数组 int x = grid[0].size(); int y = grid.size(); queue<PII> que; int size = 0;//岛屿个数 for(int i = 0;i < y; i++)//遍历数组，找到未遍历过的岛屿，即：false { for(int k = 0; k < x;k++) { if(grid[i][k] == '1' && tmp[i][k] == false) { que.push({i,k}); size++; checkgrid(que,tmp,grid); } } } return size; } };