asp网站设计代做,常州seo招聘,全球互联网总部在哪里,wordpress调用二级分类99. 岛屿数量#xff08;深搜版#xff09;
题目链接#xff1a;99. 岛屿数量
题目描述#xff1a;
给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的矩阵#xff0c;你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而…99. 岛屿数量深搜版
题目链接99. 岛屿数量
题目描述
给定一个由 1陆地和 0水组成的矩阵你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
解题思路 1、每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 2、遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。 代码
#includeiostream
#includevector
using namespace std;int dx[4] {-1,0,0,1};
int dy[4] {0,-1,1,0};
void dfs(vectorvectorint matrix, vectorvectorbool island, int r, int c)
{for(int i 0; i 4; i){int x r dx[i];int y c dy[i];if(x 0 || y 0 || x matrix.size() || y matrix[0].size() || matrix[x][y] 0 || island[x][y]) continue;island[x][y] true;dfs(matrix,island,x,y);}
}int main()
{int n , m;cin n m;vectorvectorint matrix(n2,vectorint(m2));vectorvectorbool island(n2,vectorbool(m2));for(int i 1; i n; i)for(int j 1; j m; j)cin matrix[i][j];int result 0;for(int i 1; i n; i){for(int j 1; j m; j){if(matrix[i][j] 1 !island[i][j]){result;island[i][j] true;dfs(matrix,island, i,j);}}}cout result endl;return 0;
}
99. 岛屿数量广搜版
解题思路 1、每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 2、遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。 3、加入队列就代表走过就需要标记 代码
#includeiostream
#includevector
#includequeue
using namespace std;
typedef pairint,int PII;int dx[4] {-1,0,0,1};
int dy[4] {0,-1,1,0};
void bfs(vectorvectorint matrix, vectorvectorbool island, int r, int c)
{queuePII q;q.push({r,c});while(!q.empty()){PII val q.front();q.pop();for(int i 0; i 4; i ){int x val.first dx[i], y val.second dy[i];if(x 0 || x matrix.size() || y 0 || y matrix[0].size()) continue;if(matrix[x][y] 1 !island[x][y]) {island[x][y] true;q.push({x,y});}}}
}int main()
{int n , m;cin n m;vectorvectorint matrix(n2,vectorint(m2));vectorvectorbool island(n2,vectorbool(m2));for(int i 1; i n; i)for(int j 1; j m; j)cin matrix[i][j];int result 0;for(int i 1; i n; i){for(int j 1; j m; j){if(matrix[i][j] 1 !island[i][j]){result;island[i][j] true;bfs(matrix,island, i,j);}}}cout result endl;return 0;
}
100. 岛屿的最大面积
题目链接100. 岛屿的最大面积
题目描述
给定一个由 1陆地和 0水组成的矩阵计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
解题思路 上一题的变形此时计数器统计的是每一个岛屿中1的个数因此需要放置在dfs中计数 代码
1dfs有返回
#includeiostream
#includevector
#includealgorithm
using namespace std;int dx[4] {-1, 0, 0, 1};
int dy[4] {0, -1, 1, 0};int dfs(vectorvectorint matrix, vectorvectorint visited, int r, int c)
{visited[r][c] true; // 标记当前点为已访问int area 1; // 当前格子也算一个面积单位for(int i 0; i 4; i){int x dx[i] r, y dy[i] c;// 边界检查防止越界if(x 1 || y 1 || x matrix.size()-1 || y matrix[0].size()-1) continue;if(!visited[x][y] matrix[x][y] 1){area dfs(matrix, visited, x, y); // 递归累加面积}}return area;
}int main()
{int n, m;cin n m;vectorvectorint matrix(n2, vectorint(m2));vectorvectorint visited(n2, vectorint(m2, 0)); // 初始化为未访问for(int i 1; i n; i)for(int j 1; j m; j)cin matrix[i][j];int max_area 0;for(int i 1; i n; i){for(int j 1; j m; j){if(matrix[i][j] 1 !visited[i][j]){int area dfs(matrix, visited, i, j); // 计算当前连通区域的面积max_area max(max_area, area); // 更新最大面积}}}cout max_area endl;return 0;
}2dfs无返回
#includeiostream
#includevector
#includealgorithm
using namespace std;int dx[4] {-1,0, 0, 1};
int dy[4] {0,-1,1,0};int cnt;void dfs(vectorvectorint matrix,vectorvectorint visited, int r , int c)
{cnt ;visited[r][c] true;for(int i 0; i 4; i){int x dx[i] r, y dy[i] c;if(x 0 || y 0 || x matrix.size() || y matrix[0].size()) continue;if(!visited[x][y] matrix[x][y] 1){dfs(matrix,visited,x,y);}}
}int main()
{int n, m;cin n m;vectorvectorint matrix(n2,vectorint(m2));vectorvectorint visited(n2,vectorint(m2));for(int i 1; i n; i)for(int j 1; j m; j)cin matrix[i][j];int area 0;for(int i 1; i n; i){for(int j 1; j m; j){if(matrix[i][j] 1 !visited[i][j]){cnt 0;dfs(matrix,visited,i,j);area max(area,cnt);}}}cout area endl;return 0;
}
