做文案应该关注的网站推荐,网站案例模板,html5 微网站布局,内江建设网站牛客题霸 [ 岛屿数量] C题解/答案
题目描述
给一个01矩阵#xff0c;1代表是陆地#xff0c;0代表海洋#xff0c; 如果两个1相邻#xff0c;那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿: 相邻陆地可以组成一个岛屿#xff08;相邻:上下左右#xff09;…牛客题霸 [ 岛屿数量] C题解/答案
题目描述
给一个01矩阵1代表是陆地0代表海洋 如果两个1相邻那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿: 相邻陆地可以组成一个岛屿相邻:上下左右 判断岛屿个数。
题解
人傻了调了半小时没调出来。。 难倒是不难 其实就是dfs然后标记附近的岛屿如果附近所有岛屿都被标记了就count 然后看还有其他的岛屿挺常规的
代码
class Solution {
private:int d[5]{-1,0,1,0,-1};
public:/*** 判断岛屿数量* param grid char字符型vectorvector * return int整型*/void dfs(int x, int y, vectorvectorchar grid, vectorvectorbool vis, int row, int col){if(x0||xrow||y0||ycol||vis[x][y]false) return;if(grid[x][y]1){vis[x][y] false;for(int i0;i4;i){dfs(xd[i],yd[i1],grid,vis,row,col);}}}int solve(vectorvectorchar grid) {// write code hereif(grid.size()0){return 0;}int row grid.size();int col grid[0].size();int count 0;vectorvectorbool vis(row,vectorbool(col,true));for(int i0;irow;i){for(int j0;jcol;j){if(grid[i][j]1vis[i][j]true){dfs(i,j,grid,vis,row,col);count;}}}return count;}
};
