剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

1.结果

执行结果:通过显示详情〉

执行用时:54 ms ,在所有Java提交中击败了63.77%的用户

内存消耗:39.4 MB，在所有Java提交中击败了84.15%的用户

通i过测试用例:83 /83

2.时间花费

写思路一的递归大概花了40分钟，大部分时间用来调试后面的访问标记问题。

整体跨度一天，难了就不喜欢做，一直拖。

3.思路

• 思路一：使用深度搜索

  • 递归方式

    每个点都有四个方向可以探索

    如果没索引越界、和word的对应下标的字符匹配、这个字符事先没有使用过，就递归找下一个

    • 匹配了就要把这个点标为已访问

    否则表示查找失败，此时需要注意的是：

    • 失败需要回退，即重新把这个点标识为未访问

    每次从可能的起点开始时，都需要重置那个等size的用来标记是否访问过的二维数组。

  • 栈方式

    见代码思路二，不完善，没实现

• 思路二：见代码思路二，不完善，没实现

4.code

class Solution {
    public boolean exist(char[][] board, String word) {
        /*
         * 思路一：逐个匹配，使用深度搜索，使用栈
         * 对word逐个匹配，依次入栈，每次的探寻方向有4个（实际上是3个方向，一个方向是自己走过的方向）
         * — 匹配就入栈
         * — 四个方向上都不匹配，就出栈
         * 如果栈空了，表示没找到（是最开始所有的点都试过了，就是有几个可能的起点，就空几次栈）
         * 如果匹配完了，就表示true
         * 还需要一个等size数组标记是否已经入栈
         * — 如果已经入栈，表示已经使用过了
         * 
         * 思路二：对word下手，通过坐标匹配串连，
         * 对word的每个不同字母，都找出它在矩阵的所有坐标
         * 然后一次串过去，因为是二维坐标，只要一维相等，另一维相差1，就表示相连的
         * — 如果第一个的所有方法都试过了，那就表示没找到
         * — 如果串好了，那就true
         *  — 要检查一下是否有相同的坐标存在，也可以使用相同的size来标记该坐标是否被使用 
         */

         //method 1
        int m = board.length;
        int n = board[0].length;
        int[][] flag = new int[m][n];
        char[] wordChar = word.toCharArray();
        char start = wordChar[0];
        boolean re = false;
        for(int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == start){
                    // System.out.println("START at"+" "+ i + " " + j);
                    flag[i][j] = 1;
                    for(int[] num : flag){
                        // System.out.println(Arrays.toString(num));
                    }
                    re = find(board, flag, wordChar, i, j, 1);
                    // System.out.println(re);
                    if (re) return re;
                    else{
                        flag = new int[m][n];
                    }
                }
            }
        }

        return re;
    }

    public boolean find(char[][] board,int[][] flag,char[] wordChar, int cX, int cY, int wordIdx ){
        boolean re = false;
        int m = board.length;
        int n = board[0].length;
        if (wordIdx == wordChar.length){
            return true;
        }
        if (cX - 1 >= 0 && flag[cX - 1][cY] == 0 && board[cX - 1][cY] == wordChar[wordIdx]){
            // System.out.println("up "+wordIdx);
            flag[cX-1][cY] = 1;
            re = find(board,flag,wordChar,cX-1,cY,wordIdx+1);
            if (re) return true;
            else flag[cX-1][cY] = 0;
        }
        
        if (cX + 1 < m && flag[cX + 1][cY] == 0 && board[cX + 1][cY] == wordChar[wordIdx]){
            // System.out.println("down "+wordIdx);
            flag[cX + 1][cY] = 1;
            re = find(board,flag,wordChar,cX + 1,cY,wordIdx+1);
            if (re) return true;
            else flag[cX + 1][cY] = 0;
        }
        
        if (cY- 1 >= 0 && flag[cX][cY- 1] == 0 && board[cX][cY - 1] == wordChar[wordIdx]){
            // System.out.println("left "+wordIdx);
            flag[cX][cY - 1] = 1;
            re = find(board,flag,wordChar,cX,cY - 1,wordIdx+1);
            if (re) return true;
            else flag[cX][cY - 1] = 0;
        }
        
        if (cY + 1 < n && flag[cX][cY + 1] == 0 && board[cX][cY + 1] == wordChar[wordIdx]){
            // System.out.println("right "+wordIdx);
            flag[cX][cY + 1] = 1;
            re = find(board, flag, wordChar,cX, cY + 1, wordIdx+1);
            if (re) return true;
            else flag[cX][cY + 1] = 0;
        }
        return re;
    }
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89