@@ -1620,55 +1620,6 @@ public static int LastRemaining_Solution(int n, int m) {
16201620
16211621解析:回溯法也就是特殊的dfs,需要找到所有的路径,所以每当到达边界条件或抵达目标时,递归返回,由于需要保存路径中的字母,所以递归返回时需要删除路径最后的节点,来保证路径合法。不过本题只有一个解,所以找到即可返回。
16221622
1623- public class 矩阵中的路径 {
1624- public static void main(String[] args) {
1625- char[][]arr = {{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
1626- char []str = {'b','c','c','e','d'};
1627- System.out.println(hasPath(arr, arr.length, arr[0].length, str));
1628- }
1629- static int flag = 0;
1630- public static boolean hasPath(char[][] matrix, int rows, int cols, char[] str)
1631- {
1632- int [][]visit = new int[rows][cols];
1633- StringBuilder sb = new StringBuilder();
1634- for (int i = 0;i < rows;i ++) {
1635- for (int j = 0;j < cols;j ++) {
1636- if (matrix[i][j] == str[0]) {
1637- visit[i][j] = 1;
1638- sb.append(str[0]);
1639- dfs(matrix, i, j, visit, str, 1, sb);
1640- visit[i][j] = 0;
1641- sb.deleteCharAt(sb.length() - 1);
1642- }
1643- }
1644- }
1645- return flag == 1;
1646- }
1647- public static void dfs(char [][]matrix, int row, int col, int [][]visit, char []str, int cur, StringBuilder sb) {
1648- if (sb.length() == str.length) {
1649- // System.out.println(sb.toString());
1650- flag = 1;
1651- return;
1652- }
1653-
1654- int [][]pos = {{1,0},{-1,0},{0,1},{0,-1}};
1655- for (int i = 0;i < pos.length;i ++) {
1656- int x = row + pos[i][0];
1657- int y = col + pos[i][1];
1658- if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0) {
1659- continue;
1660- }
1661- if (visit[x][y] == 0 && matrix[x][y] == str[cur]) {
1662- sb.append(matrix[x][y]);
1663- visit[x][y] = 1;
1664- dfs(matrix, x, y, visit, str, cur + 1, sb);
1665- sb.deleteCharAt(sb.length() - 1);
1666- visit[x][y] = 0;
1667- }
1668- }
1669- }
1670-
1671-
16721623
16731624## 机器人的运动范围
16741625
0 commit comments