[剑指offer] 回溯篇

JZ12 矩阵中的路径

 1 /* DFS */
 2 public class JZ12_1
 3 {
 4     public static boolean[][] vis;
 5     public static int[] dx = new int[]{-1, 1, 0, 0};
 6     public static int[] dy = new int[]{0, 0, -1, 1};
 7 
 8     public static boolean hasPath(char[][] matrix, String word)
 9     {
10         int m = matrix.length, n = matrix[0].length;
11         vis = new boolean[m][n];
12         for (int i = 0; i < m; i++)
13             for (int j = 0; j < n; j++)
14                 if (dfs(matrix, word, i, j, 0)) return true;
15         return false;
16     }
17 
18     public static boolean dfs(char[][] matrix, String word, int curX, int curY, int idx)
19     {
20         int m = matrix.length, n = matrix[0].length, nextX = -1, nextY = -1;
21         boolean res = false;
22         if (matrix[curX][curY] != word.charAt(idx)) return false;
23         if (idx == word.length() - 1) return true;
24         vis[curX][curY] = true;
25         for (int i = 0; i < 4; i++)
26         {
27             nextX = curX + dx[i];
28             nextY = curY + dy[i];
29             if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n || vis[nextX][nextY])
30                 continue;
31             res = res || dfs(matrix, word, nextX, nextY, idx + 1);
32         }
33         vis[curX][curY] = false;
34         return res;
35     }
36 }

JZ13 机器人的运动范围

 1 /* DFS */
 2 public class JZ13_1
 3 {
 4     public static boolean[][] vis;
 5     public static int[] dx = new int[]{-1, 1, 0, 0};
 6     public static int[] dy = new int[]{0, 0, -1, 1};
 7 
 8     public static int movingCount(int threshold, int rows, int cols)
 9     {
10         vis = new boolean[rows][cols];
11         return dfs(threshold, rows, cols, 0, 0);
12     }
13 
14     public static int dfs(int threshold, int m, int n, int curX, int curY)
15     {
16         int nextX = -1, nextY = -1, res = 1;
17         vis[curX][curY] = true;
18         for (int i = 0; i < 4; i++)
19         {
20             nextX = curX + dx[i];
21             nextY = curY + dy[i];
22             if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n || vis[nextX][nextY] || cal(nextX) + cal(nextY) > threshold)
23                 continue;
24             res += dfs(threshold, m, n, nextX, nextY);
25         }
26         return res;
27     }
28 
29     public static int cal(int nums)
30     {
31         int res = 0;
32         while (nums != 0)
33         {
34             res += nums % 10;
35             nums /= 10;
36         }
37         return res;
38     }
39 }