DFS、BFS详解之二维矩阵路径问题

前言

印象中初次碰到DFS算法是在图的相关问题中，比如图的最短路径中；对于BFS算法，我初次接触是在二叉树的层序遍历.DFS算法在与我接触的算法中与其最像的就是回溯算法。两者的区别在于：DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置。

1、机器人的运动范围

这道题不用DFS深度优先算法也是可以解出来的，直接用模拟遍历即可。

解法1：DFS解法

class Solution {
    int m,n,k;
    public int movingCount(int m, int n, int k) {
        boolean [][] visited=new boolean[m][n];
        this.m=m;
        this.n=n;
        this.k=k;
        return dfs(0,0,visited);
    }
    public int dfs(int i,int j,boolean [][]visited)
    {
        if(i<0 || j<0 || i>=m || j>=n || isValid(i,j)>k ||visited[i][j])
        {
            return 0;
        }
        visited[i][j]=true;
        return 1+dfs(i+1,j,visited)+dfs(i,j+1,visited);
    }
    private int isValid(int i,int j)
    {
        int sum=0;
        while(i>0)
        {
            sum+=i%10;
            i=i/10;
        }
        while(j>0)
        {
            sum+=j%10;
            j=j/10;
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

这道题猛然一看是不难的，但是是有许多门道在里面的，我们要防止的是一种什么现象呢？就是一个点满足数位和条件，但是由于前面的某些数不满足数位和条件，导致其不可达，为什么呢？问题出在这个数位和上，数位和并不反应真实的大小关系，在后的位置可能数位很小，举个例子(0,6)与（0,10)的数位和分别是6与1在k=6的情况下，(0,6)可达但是由于(0,7),(0,8)的不可达，导致(0,10)不可达。

详细的代码执行过程：
以2x3的矩阵以及k=1为例：DFS算法首先从(0,0)开始，然后走到(1,0)，符合条件，走到(2,0)发现不符合条件，return 0这时候产生归操作，代码回归到return 1+dps(i+1,j,visited)+dps(i,j+1,visited)，这个时候i=1,j=0,从而进入到dps(i,j+1,visited) 再次进入递操作，(i,j)=(1,1)，发现不符合，再次触发return 0操作，这个时候(i=1,j=0)，从而代码回到return 1+dps(i+1,j,visited)+dps(i,j+1,visited)，再次归到上一栈(i,j)=(0,0)，注意这时候的这一栈是谁压进去的，是dps(i+1,j,visited)压进去的，所以这时候我们再次进入到dps(i,j+1,visited)，再次进入递操作(i,j)=(0,1),满足条件，再次进入，则进入dps(i+1,j,visited)发现(i,j)=(1,1)发现不符合，触发return 0;再次回到return 1+dps(i+1,j,visited)+dps(i,j+1,visited)，这个时候(i,j)=(0,1)从而进入dps(i,j+1,visited),(i,j)=(0,2)，发现不满足，再次触发return 0操作，从而整个栈弹出完毕，递归结束。

值得注意的是：我们在其中并没有访问所有的节点，就拿2x3的矩阵举例：我们访问的有效的节点有(0,0),(1,0),(1,1),(0,1),(0,2)而没有访问(1,2)(2,2)这两个点。

解法2：模拟遍历

模拟遍历特别要注意的是什么，注意各个点之间的粘性，这个节点能否可达其实是依赖于上一个节点的，这有一点像动态规划中的状态转移方程,注意在模拟中一定要赋初值，从而给初始的触发信号。

class Solution {
    public int movingCount(int m, int n, int k) {
    int  [][] visited=new int[m][n];
    int ans=0;
    visited[0][0]=1;
    for(int i=0;i<m;i++)
    {
    	for(int j=0;j<n;j++)
    	{
    		if(!isValid(i,j,k))
    		{
    			continue;
    		}
    		if(i>=1)
    		{
    			visited[i][j]|=visited[i-1][j];
    		}
    		if(j>=1)
    		{
    			visited[i][j]|=visited[i][j-1];
    		}
    		if(i+1<m)
    		{
    			visited[i][j]|=visited[i+1][j];		
    		}
    		if(j+1<n)
    		{
    			visited[i][j]|=visited[i][j+1];		
    		}
    		ans+=visited[i][j];
    	}
    }
    return ans;
    }
     private boolean isValid(int i,int j,int k)
    {
        int sum=0;
        while(i>0)
        {
            sum+=i%10;
            i=i/10;
        }
        while(j>0)
        {
            sum+=j%10;
            j=j/10;
        }
        return sum<=k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

解法3：BFS解法

2、矩阵中的路径

这道题可以给我们一个很大的启发，这道题属于没有出发点没有终止点，查找的区域是整个矩阵，从那一点开始与结束都可以，所以我们怎么保证整个矩阵都搜索到呢，我们采取二次循环遍历整个矩阵中每个节点的方式，从而保证任何一点开始与任何一点终止的情况都被我们包含到。

可以发现这道题与上面的题目不同，这一道题其实更像回溯算法，因为我们最后做了visited的撤销操作。如果不做撤销，这道题的答案就是错的，原因在于我们可能从不同的出发点来寻找可能满足条件的矩阵路径，如果不回溯的话，上次经过的点这次就不能经过了，这显然是不对的。

写法1：多次dfs

class Solution {
    String word;
    boolean res;
    public boolean exist(char[][] board, String word) {
        this.word=word;
        boolean [][] visited=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[0].length;j++)
            {
                if(dfs(board,i,j,0,visited))
                {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,int k,boolean [][]visited)
    {
        //如果遇到下一个的字符与String中的字符不等，可以直接终止。
        if(i<0 || j<0 || i>=board.length || j>=board[0].length || board[i][j]!=word.charAt(k) || visited[i][j])
        {
            return false;
        }
        if(k==word.length()-1)
        {
            return true;
        }
        visited[i][j]=true;
        boolean res=dfs(board,i-1,j,k+1,visited) || dfs(board,i+1,j,k+1,visited)|| dfs(board,i,j-1,k+1,visited) || dfs(board,i,j+1,k+1,visited);
        visited[i][j]=false;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

写法2：for循环遍历4个方向

class Solution {
    String word;
    boolean res;
    public boolean exist(char[][] board, String word) {
        this.word=word;
        boolean [][] visited=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[0].length;j++)
            {
                if(dfs(board,i,j,0,visited))
                {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,int k,boolean [][]visited)
    {
        //如果遇到下一个的字符与String中的字符不等，可以直接终止。
        if(board[i][j]!=word.charAt(k) || visited[i][j])
        {
            return false;
        }
        if(k==word.length()-1)
        {
            return true;
        }
        visited[i][j]=true;
        int[] dirs=new int[]{0,1,0,-1,0};
        for(int dir=0;dir<4;dir++)
        {
        	int newi=i+dirs[dir];
        	int newj=j+dirs[dir+1];
      	    if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length)
      	    {
      	    	res=dfs(board,newi,newj,k+1,visited);	
      	    }
      	    if(res)
      	    {
      	    	return true;
      	    }
        }
        visited[i][j]=false;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

这道题我在一开始没有反应过来，我使用visited的时候不敢说直接visited=true后直接返回，所以有下面很蠢的书写方式，但是这个方式就间接应征了上面书写方式的正确。

class Solution {
    String word;
    boolean res;
    public boolean exist(char[][] board, String word) {
        this.word=word;
        boolean [][] visited=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[0].length;j++)
            {
                if(dfs(board,i,j,0,visited))
                {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,int k,boolean [][]visited)
    {
        //如果遇到下一个的字符与String中的字符不等，可以直接终止。
        if(i<0 || j<0 || i>=board.length || j>=board[0].length || board[i][j]!=word.charAt(k))
        {
            return false;
        }
        if(k==word.length()-1)
        {
            return true;
        }
        visited[i][j]=true;
        boolean res=false;
        if(i>=1 &&!visited[i-1][j] )
        {
            res=res || dfs(board,i-1,j,k+1,visited);
        }
        if(i+1<board.length && !visited[i+1][j])
        {
             res=res || dfs(board,i+1,j,k+1,visited);
        }
        if(j>=1 && !visited[i][j-1] )
        {
            res=res || dfs(board,i,j-1,k+1,visited);
        }
        if(j+1<board[0].length && !visited[i][j+1])
        {
            res=res || dfs(board,i,j+1,k+1,visited);
        }
        visited[i][j]=false;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

矩阵中的最长递增路径

解法1：动态规划法

这一道题能够使我联想起来的一道题是动态规划中的最长递增子序列，那么这一道题能不能用动态规划去做呢？是可以的，重点在于其中的状态定义与状态转移，状态转移是比较简单的，重点在状态的定义会影响到条件的判断

dp[i][j]定义为以(i,j)为终点的最长递增路径
则状态转移方程可以写为：dp[i][j]=Math.max(dp[i][j],dp[prei][prej]+1);

class Solution {
    int [] dirs=new int[]{0,-1,0,1,0};
    public int longestIncreasingPath(int[][] matrix) {
        //这道题我的难点在什么地方
        int m=matrix.length;
        int ans=0;
        int n=matrix[0].length;
        int [][]dp=new int[m][n];
        for(int i=0;i<m;i++)
        {
            Arrays.fill(dp[i],1);
        }
        // 为了整体信息的排序，需要将节点的位置与数值都作为元素存入list节点中
        List<int[]> list=new ArrayList<>();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                list.add(new int[]{matrix[i][j],i,j});
            }
        }
        list.sort(new Comparator<int []>(){
            public int compare(int []o1,int []o2)
            {
                return o1[0]-o2[0];
            }
        });
        for(int k=0;k<list.size();k++)
        {
            int i=list.get(k)[1];
            int j=list.get(k)[2];
            for(int dir=0;dir<4;dir++)
            {
                int prei=i+dirs[dir];
                int prej=j+dirs[dir+1];
                if(prei>=0 && prej>=0 &&  prei<m && prej<n && matrix[prei][prej]<matrix[i][j])
                {
                    dp[i][j]=Math.max(dp[i][j],dp[prei][prej]+1);
                }
            }
            ans=Math.max(ans,dp[i][j]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

解法2：DFS+记忆化

记忆化这个东西，我们早就在用了，在前面的动态规划中，我们就开始用记忆化矩阵，不过那个时候叫备忘录来降低时间复杂度。这个备忘录矩阵兼顾了访问与为访问的标记值，就如同下面的普通dfs。

class Solution {
    int []dirs=new int[]{0,-1,0,1,0};
        int ans=1;
    public int longestIncreasingPath(int[][] matrix) {
        int [][] visited=new int [matrix.length][matrix[0].length];
    
        for(int i=0;i<matrix.length;i++)
        {
            for(int j=0;j<matrix[0].length;j++)
            {
                if(visited[i][j]==0)
                {
                ans=Math.max(ans,dfs(i,j,matrix,visited));
                }
            }
        }
        return ans;
    }
    public int dfs(int i,int j, int [][] matrix,int[][] visited)
    {
        if(visited[i][j]!=0)
        {
            return visited[i][j];
        }
        int res=1;
        for(int dir=0;dir<4;dir++)
        {
            int newi=i+dirs[dir];
            int newj=j+dirs[dir+1];
            if (newi >= 0 && newi < matrix.length && newj >= 0 && newj < matrix[0].length && matrix[newi][newj]>matrix[i][j])
            {
                res=Math.max(res,1+dfs(newi,newj,matrix,visited));
            }
        }
        visited[i][j]=res;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

解法3（超时）：单纯DFS+回溯

class Solution {
    int []dirs=new int[]{0,-1,0,1,0};
    int ans=1;
    public int longestIncreasingPath(int[][] matrix) {
        boolean [][] visited=new boolean [matrix.length][matrix[0].length];
    
        for(int i=0;i<matrix.length;i++)
        {
            for(int j=0;j<matrix[0].length;j++)
            {
                ans=Math.max(ans,dfs(i,j,matrix,visited));
            }
        }
        return ans;
    }
    public int dfs(int i,int j, int [][] matrix,boolean [][] visited)
    {
        if(visited[i][j])
        {
            return 0;
        }
        int res=1;
        visited[i][j]=true;
        for(int dir=0;dir<4;dir++)
        {
            int newi=i+dirs[dir];
            int newj=j+dirs[dir+1];
            if (newi >= 0 && newi < matrix.length && newj >= 0 && newj < matrix[0].length && matrix[newi][newj]>matrix[i][j])
            {
                res=Math.max(res,1+dfs(newi,newj,matrix,visited));
            }
        }
        visited[i][j]=false;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36