【剑指Offer 12】矩阵中的路径

1. /**
2. * 剑指 Offer 12. 矩阵中的路径
3. * https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/
4. *
5. * 思路：深度优先搜索
6. * */
7. public class Solution {
8.     private char[][] board;
9.     private String word;
10.     private int m;
11.     private int n;
12.     private boolean[][] marked;
14.     public boolean exist(char[][] board, String word) {
15.         this.board = board;
16.         this.word = word;
17.         m = board.length;
18.         n = board[0].length;
19.         marked = new boolean[m][n];
21.         for (int i = 0; i < m; i++) {
22.             for (int j = 0; j < n; j++) {
23.                 if (board[i][j] != word.charAt(0)) {
24.                     continue;
25.                 }
26.                 if(dfs(i, j, 0)) {
27.                     return true;
28.                 }
29.             }
30.         }
31.         return false;
32.     }
34.     private boolean dfs(int i, int j, int index) {
35.         if (index == word.length()) {
36.             return true;
37.         }
38.         if (i < 0 || i >= m || j < 0 || j >= n) {
39.             return false;
40.         }
41.         if (marked[i][j] == true || board[i][j] != word.charAt(index)) {
42.             return false;
43.         }
44.         marked[i][j] = true;
45.         index++;
46.         boolean result = dfs(i + 1, j, index)
47.                 || dfs(i - 1, j, index)
48.                 || dfs(i, j + 1, index)
49.                 || dfs(i, j - 1, index);
50.         marked[i][j] = false;
51.         return result;
52.     }
53. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！