【算法】回溯法四步走 (10)

回溯还原现场：
path--; // 回溯法关键步骤
a[m][n] = 0;

//青蛙跳 public class Sy1 { static int count = 0; // 跳法种类计数 static int x = 4, y = 4; // 目的坐标 static int step = 0; // 记录步数 // 地图，0代表没有走过，1 代表已经走过 static int[][] map = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; static int min = 25; // 用来记录最小步数 static int sx[] = new int[25], sy[] = new int[25]; // 记录坐标 // 求解总共跳法，并求出最短步数，方便下面列出路径 static void jump(int m, int n) { // 该点在地图边界之外或者走过 if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { return; } map[m][n] = 1; // 走到此节点 step++; if (m == x && n == y) { // 如果到达目的地 if (step < min)// 更新最短步数 min = step; count++; } // 所有路径 jump(m + 1, n); // 右跳 jump(m - 1, n); // 左跳 jump(m, n + 1); // 下跳 jump(m, n - 1); // 上跳 step--; // 回溯法关键步骤 map[m][n] = 0; } // 列出最短步数的路径 static void find(int m, int n) { // 该点在地图边界之外或者走过 if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { return; } // 记录坐标 sx[step] = m; sy[step] = n; // 走到此节点 map[m][n] = 1; step++; if (m == x && n == y && step == min) { // 到达目的且为最短路径 int p = min - 1; System.out.print("最短 path:" + p + "步"); for (int i = 0; i < min; i++) System.out.print("(" + sx[i] + "," + sy[i] + ")"); System.out.println(); } find(m + 1, n); find(m - 1, n); find(m, n + 1); find(m, n - 1); step--; map[m][n] = 0; } public static void main(String[] args) { jump(0, 0); step = 0; System.out.println("总共" + count + "种解法"); find(0, 0); } }

程序运行结果：

走迷宫

以一个 M×N 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。
设计一个程序，对任意输入的迷宫，输出一条从入口到出口的通路，或得出没有通路的结论。
例：
输入：
请输入迷宫的行数 9
请输入迷宫的列数 8
请输入 9 行 8 列的迷宫
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0

为了方便大家观看，我换成了矩阵：
\[ \begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix} \]

输出：
有路径
路径如下：
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #

为了方便大家观看，我换成了矩阵：
\[ \begin{matrix} \# & \# & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & \# & 1 & 0 & 0 & 0 & 1 & 0 \\ \# & \# & 1 & 0 & 1 & 1 & 0 & 1 \\ \# & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ \# & \# & \# & 1 & \# & \# & \# & 0 \\ 0 & 1 & \# & \# & \# & 1 & \# & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & \# & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & \# & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & \# & \# \\ \end{matrix} \]

答案：这里用栈来实现的递归，算是一个新思路。

//迷宫 /*位置类*/ class Position { int row; int col; public Position() { } public Position(int row, int col) { this.col = col; this.row = row; } public String toString() { return "(" + row + " ," + col + ")"; } } /*地图类*/ class Maze { int maze[][]; private int row = 9; private int col = 8; Stack<Position> stack; boolean p[][] = null; public Maze() { maze = new int[15][15]; stack = new Stack<Position>(); p = new boolean[15][15]; } /* * 构造迷宫 */ public void init() { Scanner scanner = new Scanner(System.in); System.out.println("请输入迷宫的行数"); row = scanner.nextInt(); System.out.println("请输入迷宫的列数"); col = scanner.nextInt(); System.out.println("请输入" + row + "行" + col + "列的迷宫"); int temp = 0; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp = scanner.nextInt(); maze[i][j] = temp; p[i][j] = false; } } } /* * 回溯迷宫，查看是否有出路 */ public void findPath() { // 给原始迷宫的周围加一圈围墙 int temp[][] = new int[row + 2][col + 2]; for(int i = 0; i < row + 2; ++i) { for(int j = 0; j < col + 2; ++j) { temp[0][j] = 1; temp[row + 1][j] = 1; temp[i][0] = temp[i][col + 1] = 1; } } // 将原始迷宫复制到新的迷宫中 for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp[i + 1][j + 1] = maze[i][j]; } } // 从左上角开始按照顺时针开始查询 int i = 1; int j = 1; p[i][j] = true; stack.push(new Position(i, j)); while (!stack.empty() && (!(i == (row) && (j == col)))) { if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) { p[i][j + 1] = true; stack.push(new Position(i, j + 1)); j++; } else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) { p[i + 1][j] = true; stack.push(new Position(i + 1, j)); i++; } else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) { p[i][j - 1] = true; stack.push(new Position(i, j - 1)); j--; } else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) { p[i - 1][j] = true; stack.push(new Position(i - 1, j)); i--; } else { stack.pop(); if(stack.empty()) { break; } i = stack.peek().row; j = stack.peek().col; } } Stack<Position> newPos = new Stack<Position>(); if (stack.empty()) { System.out.println("没有路径"); } else { System.out.println("有路径"); System.out.println("路径如下："); while (!stack.empty()) { Position pos = new Position(); pos = stack.pop(); newPos.push(pos); } } /* * 图形化输出路径 * */ String resault[][]=new String[row+1][col+1]; for(int k=0; k<row; ++k) { for(int t=0; t<col; ++t) { resault[k][t]=(maze[k][t])+""; } } while (!newPos.empty()) { Position p1=newPos.pop(); resault[p1.row-1][p1.col-1]="#"; } for(int k=0; k<row; ++k) { for(int t=0; t<col; ++t) { System.out.print(resault[k][t]+"\t"); } System.out.println(); } } } /*主类*/ class Sy4 { public static void main(String[] args) { Maze demo = new Maze(); demo.init(); demo.findPath(); } }