建模外包网站,量品定制怎么发展客户,网站开发时间,静态网站模板二#xff1a;思路
1.这里我们使用的是BFS(广度优先搜索遍历) 2.当我们遇到一个岛屿#xff08;‘1’#xff09;的时候#xff0c;我们就对其的左右四边进行广度遍历 并且标记已经访问过的结点。 3.那么我们每次遇到一个1开始广度遍历那就证明我们发现了一个岛
三:上码 …
二思路
1.这里我们使用的是BFS(广度优先搜索遍历) 2.当我们遇到一个岛屿‘1’的时候我们就对其的左右四边进行广度遍历 并且标记已经访问过的结点。 3.那么我们每次遇到一个1开始广度遍历那就证明我们发现了一个岛
三:上码
class Solution {
public:int numIslands(vectorvectorchar grid) {/**思路1.这里我们使用的是BFS(广度优先搜索遍历)2.当我们遇到一个岛屿1的时候我们就对其的左右四边进行广度遍历并且标记已经访问过的结点。3.那么我们每次遇到一个1开始广度遍历那就证明我们发现了一个岛 */int m grid.size(); //表示矩阵的行int n grid[0].size();// //表示矩阵的列int num_islands 0;//表示岛屿的数量for(int i 0; i m; i){for(int j 0; j n; j){queuepairint,int q;//创建一个队列可以存两个值行和列if(grid[i][j] 1){q.push({i,j});grid[i][j] 0;//访问过的话将其设置为 0 num_islands;} while(!q.empty()){ auto temp q.front();//这里的auto可以表示任何类型所以当然包括我们的一个集合q.pop();int nr temp.first;//集合的第一个元素行int nc temp.second;//集合的第二个元素列//接下来看该位置的四周的值是否为1为1的话那么接下来就扩大 岛屿的值//该位置的上方if(nr - 1 0 grid[nr-1][nc] 1){q.push({nr-1,nc});grid[nr-1][nc] 0;} //该位置的下方(这里小于 m,是因为我们的二维矩阵边界行的最大值为 m - 1 指的是在二维矩阵中的下标)if(nr 1 m grid[nr1][nc] 1){q.push({nr1,nc});grid[nr1][nc] 0;}//该位置的左方if(nc - 1 0 grid[nr][nc-1] 1){q.push({nr,nc-1});grid[nr][nc-1] 0;}//该位置的右方if(nc 1 n grid[nr][nc1] 1){q.push({nr,nc1});grid[nr][nc1] 0;}}}}return num_islands;}
};
