DFS深度搜索leetcode200

女爷i 2022-02-22 15:50 137阅读 0赞

DFS深度搜索是什么？怎么做？用途？

举例 LeetCode200，给定一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

**示例 1:**

输入:
    11110
    11010
    11000
    00000
    
    输出: 1

*  思路是，用一个标记的mark二维数组保存访问过的点，未访问置0，访问后置1.然后从第一个节点开始遍历（当然我们可以从任意一个节点开始遍历），每次判断mark数组里的位置是否为被访问，同时判断是否是山就是1（if(mark\[i\]\[j\]==0&&grid\[i\]\[j\]=='1'）就是能访问，那么从这个点开始深度搜索，同时岛屿加1.那么从这个地方开始深度遍历周围的节点，终止一定周围都为0时，回退到之前第一个开始递归的地方。根据题意，只要岛屿的1连在一起便是为一处。然后还有一个点就是，每次遍历访问过的点都要mark\[i\]\[j\]都要置1.

DFS深度函数：先标记访问过的点x,y，再对这个点进行遍历上下左右，如果某个点情况不满足，则跳过这个点，若某个点情况满足，则当时就从该进行递归DFS，标记这个点开始的mark数组。

以下是实现代码

package com.hnist.leetcode;
    
    public class DFStest {
    
        static int dx[] = {-1,1,0,0};
        static int dy[] = {0,0,-1,1};
    
        public int numIslands(char[][] grid) {
    
            //行
            int m = grid.length;
            //列
            int n = grid[0].length;
            //标记二维数组
            int[][] mark = new int[m][n];
            //岛屿数
            int island = 0;
            //从起始点开始遍历
            for(int i=0;i<grid.length;i++){
    
                for(int j= 0;j<grid[i].length;j++){
                    //当某个点满足再加1，那么这个附近的点会被深度遍历到一起
                    if(mark[i][j]==0&&grid[i][j]=='1'){
                        DFS(grid,mark,i,j);
                        island++;
                    }
    
                }
    
            }
                    return island;
        }
    
        /*
        *这个深度遍历函数
        */
        public void DFS(char[][] grid,int[][] mark,int x,int y){
    
                //标记当前访问过的点
            mark[x][y] = 1;
                //从当前点开始遍历周围的点
            for(int i=0;i<4;i++){
    
                int newx = dx[i]+x;
    
                int newy = dy[i]+y;
                
                //如果当前的点不满足，便跳过
                if(newx<0||newx>=mark.length||newy<0||newy>=mark[newx].length){
    
                    continue;
                }
                //当前点满足，便会从当前的邻接点开始继续深度递归遍历下去
                if(mark[newx][newy]==0&&grid[newx][newy]=='1'){
    
                    DFS(grid,mark,newx,newy);
                }
    
            }
    
        }
    
        }