Problem: 3459. 最长 V 形对角线段的长度

思路

本题的实质就是有限制条件的图的DFS，以及利用记忆化搜索减少重复计算。

在设计dfs的时候，每次遍历到一个点，都先判断能不能直行，如果能直行，则直行走到尽头，每直行一步，更新一下最大线段的长度。直行到尽头之后，退回一步，尝试向右转，直到右转到达尽头，右转过程中也更新线段的最大长度。右转到尽头后，再往回退一步，重复以上步骤，每一步都更新线段的长度，直到回到出发点。这时就求出最大的线段长度了。 设线段最大长度为l。例如下图中，从1出发，直行，直行到2，直到尽头3，更新l=3。接着回溯到2，这时该向右转了，到达4，到达5，更新l=4。接着再回溯到1，向右转到达6，l没有更新。因此，执行一次dfs就能求出从该点出发可达的最大线段长度。

img

这时我们回到题目，将题目场景带入以上的dfs。出发点是grid[i][j]为1的位置，而往哪个方向走，什么时候能直行，什么时候能右转呢？这个就是dfs的限制条件，我们需要在设计dfs的时候传入参数。

我们设dfs函数为dfs(i,j,k,isTurn,target,grid,memory)。其中k,isTurn,target为限制条件，memory用来存储已经遍历过的中间结果。

  • (i,j）表示上一步的位置
  • k表示直行或者右转的方向下标。方向数组为，pos = {{-1,-1}, {-1,1}, {1,1,}, {1,-1}}，那么（post[k][0],post[k][1]）表示直行的方向。而右转的方向为（post[(k+1)%4][0],post[(k+1)%4][1]）。
  • isTurn表示能不能右转。true能右转，false不能。
  • target表示下一步的预期值，通过2-target实现更新。
  • grid为二维矩阵。
  • memory是一个三维矩阵，用于存储已经遍历过点的结果。int[][][] memory = new int[n][m][1 << 3]。memo[i][j][mask]含义是从(i,j)出发在mask状态下能到达的最大路径长度。在本题目中，mask共有8个状态，包含四个方向，两个走法（直行和右转），我们用最低位表示走法，最高两位表示方向。

在dfs函数主体中，先设计递归终止条件，然后dfs搜索直行时的最大长度和dfs搜索右转时的最大长度，两者取最大值返回。同时更新memory中间结果。

到这，我们就设计好了我们的dfs函数。

复杂度

  • 时间复杂度: O(m∗n)∗8=O(m∗n)（每个点最多被遍历8次）

  • 空间复杂度: O(m∗n)∗8=O(m∗n)

Code

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
class Solution {
    private static final int[][] pos = {{-1,-1}, {-1,1}, {1,1,}, {1,-1}};

    public int lenOfVDiagonal(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        /* 记忆化搜索，memo[i][j][mask]含义是从(i,j)出发在mask状态下能到达的最大路径长度，
        mask共有8个状态，包含四个方向，两个走法（直行和右转），最低位表示走法，最高两位表示方向
        */
        int[][][] memory = new int[n][m][1 << 3];

        for(int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                if(grid[i][j] == 1){
                    for(int k = 0;k < 4;k ++){
                        ans = Math.max(ans, dfs(i,j,k,true,2, grid,memory) + 1);
                    }
                }
            }
        }
        return ans;
    }

    // (i,j)为上一步的位置，k为直行或者右转的方向，isTurn表示是否能够转弯，target表示当前位置需要的值是0还是2
    private int dfs(int i, int j, int k, boolean isTurn,int target,int[][] grid,int[][][] memory){
        i += pos[k][0];
        j += pos[k][1];
        // 递归终止条件
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != target){
            return 0;
        }

        int c = isTurn ? 1 : 0;
        int mask = k << 1 | c;
        if(memory[i][j][mask] != 0){
            return memory[i][j][mask];
        }

        // 直行
        int result = dfs(i,j,k,isTurn,2 - target,grid,memory) + 1;
        // 右转
        if(isTurn){
            result = Math.max(result, dfs(i,j,(k + 1) % 4,false,2 - target, grid,memory) + 1);
        }
        return memory[i][j][mask] = result;
       

    }
}