任务日期：8.2

题目一链接：99. 岛屿数量 (kamacoder.com)

思路：主函数：将题目里的数据放入一个矩阵graph里，然后遍历graph，遇见没有遍历过的陆地就result + 1同时dfs当前节点。dfs函数：此题就一个递归终止条件所以不用写确定递归终止的条件，然后确定单层递归逻辑，分别向上右下左四个方向进行递归，符合条件的继续下一层递归。

代码：

#include  using namespace std; //思路：用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。 int dir[4][2] = {0,1,1,0,0,-1,-1,0};//上右下左 void dfs(const vector> &gragh,vector> &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> gragh(n + 1,vector(m + 1,0));     //将题目输入数据记录到一个邻接矩阵中     for(int i = 0;i < n;i ++) {         for(int j = 0;j < m;j ++) {             cin>>gragh[i][j];         }     }     //定义一个记录已经被标记的陆地的邻接矩阵     vector> visited(n + 1,vector(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  using namespace std; //思路：遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。 int dir[4][2] = {0,1,1,0,0,-1,-1,0}; void bfs(vector> &grid,vector> &visited,int x,int y) {     //确定递归终止条件：遍历的下一层是被标记的点或者是海洋     //确定单层递归逻辑     std::queue> que;     que.push({x,y});//队列用push就行     visited[x][y] = true;//压入到队列中就标记点x,y，否则某一点会重复加入进队列里     while(!que.empty()) {         pair 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> grid(n + 1,vector(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> visited(n + 1,vector (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<