阅读量:0
任务日期：8.2
题目一链接：99. 岛屿数量 (kamacoder.com)
思路：主函数：将题目里的数据放入一个矩阵graph里，然后遍历graph，遇见没有遍历过的陆地就result + 1同时dfs当前节点。dfs函数：此题就一个递归终止条件所以不用写确定递归终止的条件，然后确定单层递归逻辑，分别向上右下左四个方向进行递归，符合条件的继续下一层递归。
代码：
#include <bits/stdc++.h> using namespace std; //思路：用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。 int dir[4][2] = {0,1,1,0,0,-1,-1,0};//上右下左 void dfs(const vector<vector<int>> &gragh,vector<vector<bool>> &visited,int x,int y) { //确定递归终止条件:不需要再写，因为终止条件在下面的if语句里了；一道题一般有两个终止条件，一个是这里一个在下面 //if(visited[x][y] || gragh[x][y] == 0) return;//如果当前点被遍历过或者是海水，则终止递归 //确定当前层递归逻辑：到下一层的过程 for(int i = 0;i < 4;i ++) {//依次遍历四个位置 int nextx = x + dir[i][0];//每个位置的第一个数控制x int nexty = y + dir[i][1];//每个位置的第一个数控制y if(nextx < 0 || nextx >= gragh.size() || nexty < 0 || nexty >= gragh[0].size()) continue;//如果越界则跳过这个点 if(gragh[nextx][nexty] == 1 && !visited[nextx][nexty]) {//如果当前节点及时陆地又没被标记 visited[nextx][nexty] = true;//先标记 dfs(gragh,visited,nextx,nexty);//沿当前方向继续下一层递归 } } } int main() { int n,m; cin>>n>>m; std::vector<vector<int>> gragh(n + 1,vector<int>(m + 1,0)); //将题目输入数据记录到一个邻接矩阵中 for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { cin>>gragh[i][j]; } } //定义一个记录已经被标记的陆地的邻接矩阵 vector<vector<bool>> visited(n + 1,vector<bool>(m + 1,false));//visited数组的类型是bool并且初始化为false int result = 0;//记录结果 //遍历邻接矩阵graph for(int i = 0;i < n;i ++) {//遍历整个gragh,寻找没有遍历过得陆地 for(int j = 0;j < m;j ++) { if(gragh[i][j] == 1 && !visited[i][j]) {//遇到一个没有遍历过的陆地 result ++;//计数器就加一 visited[i][j] = true;//标记已经遍历的点 dfs(gragh,visited,i,j);//然后把该节点陆地所能遍历到的陆地都标记上。 } } } std::cout << result << std::endl; return 0; }难点：1.visited矩阵是bool类型，注意传递参数使得数据类型
2.一般dfs里面有两个终止递归的地方，一个在确定递归终止条件里，一个在确定单层递归逻辑里，如果当前限制条件较少，这两个终止条件只能写一个，否则答案会错误。
3.dir二维数组，弄清下标的意义。
题目二链接：99. 岛屿数量 (kamacoder.com)
思路：遇到一个没有遍历过的节点陆地，计数器就加一，然后标记该节点陆地所能遍历到的所有陆地。主函数：将题目的数组放入到二维数组grid中，然后遍历grid数组中的每一个点，如果发现一个没有被标记的陆地则result + 1并且标记和bfs当前节点。bfs:同上省略确定递归终止条件的一步，在确定当前层函数时首先创建一个队列（用来实现外圈一圈一圈地遍历），将当前点加入到队列中，然后遍历当前节点一周的节点（体现bfs:内圈一圈一圈地遍历），然后将符合条件的节点压入队列中并标记，然后在弹出队列中的元素一圈一圈的遍历循环往复一直到队列为空。
代码：
#include <bits/stdc++.h> using namespace std; //思路：遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。 int dir[4][2] = {0,1,1,0,0,-1,-1,0}; void bfs(vector<vector<int>> &grid,vector<vector<bool>> &visited,int x,int y) { //确定递归终止条件：遍历的下一层是被标记的点或者是海洋 //确定单层递归逻辑 std::queue<pair<int,int>> que; que.push({x,y});//队列用push就行 visited[x][y] = true;//压入到队列中就标记点x,y，否则某一点会重复加入进队列里 while(!que.empty()) { pair<int,int> cur = que.front(); que.pop(); for(int i = 0;i < 4;i ++) {//遍历当前节点的四周一圈的节点 int nextx = cur.first + dir[i][0]; int nexty = cur.second + dir[i][1]; if(nextx < 0 || nextx == grid.size() || nexty < 0 || nexty == grid[0].size()) continue; if(grid[nextx][nexty] == 1 && !visited[nextx][nexty]) { que.push({nextx,nexty});//四个方向的节点都加入到队列中，一圈一圈地遍历，同时还不用管顺序 visited[nextx][nexty] = true; } } } } int main() { int n,m; cin>>n>>m; vector<vector<int>> grid(n + 1,vector<int>(m + 1,0)); for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { cin>>grid[i][j]; } } int result = 0; vector<vector<bool>> visited(n + 1,vector<bool> (m + 1,false)); //遍历grid for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { if(grid[i][j] == 1 && !visited[i][j]) { result ++; visited[i][j] = true; bfs(grid,visited,i,j); } } } cout<<result; return 0; }难点：1.进入bfs后先创建一个队列并将当前节点加入队列同时标记该节点
2.在节点压入队列时就标记改点
3.队列控制外圈一圈一圈地遍历，for循环控制内圈一圈一圈地遍历。
4.此题不用管遍历时每一圈的顺序，所以用队列或者栈都行
5.bfs在形式上与dfs的区别就是bfs一圈一圈地遍历，这里包括外圈和内圈。
