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

程序运行结果：

嘿嘿，上面的那种用栈来实现递归的方法是不是看完了呢！把它放在第一个就是为了让大家以为没有递归回溯的答案，好认认真真的看完。。。（别打我）
贴心的我当然准备了用递归回溯方法的代码：

// 迷宫 class Sy4 { public static void main(String[] args) { Demo demo = new Demo(); demo.init(); demo.find(0, 0); } } class Demo { int m, n; // 类在实例化时分配空间，但是只是逻辑上连续的空间，而不一定是物理上，毕竟有静态变量，不可能完全连续。 String[][] maze; //不能用char，扫描器Scanner不能扫描。 //这里只是声明，后面输入m、n时才能确定分配空间的大小 //初始化迷宫 public void init() { Scanner scanner = new Scanner(System.in); System.out.println("请输入迷宫的行数"); m = scanner.nextInt(); System.out.println("请输入迷宫的列数"); n = scanner.nextInt(); maze = new String[m][n]; System.out.println("请输入" + m + "行" + n + "列的迷宫"); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { maze[i][j] = scanner.next(); } } System.out.println("--------------------------------------------------------"); System.out.println("迷宫如下："); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { System.out.print(maze[i][j] + " "); } System.out.println(); } System.out.println("--------------------------------------------------------"); } //走到(x, y)点，找找路径 public void find(int x, int y) { if (x < 0 || y < 0 || x >= m || y >= n || !maze[x][y].equals("0")) { // 注意字符串要用equals return; } maze[x][y] = "#"; // 走到此节点 if (x == m - 1 && y == n - 1) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { System.out.print(maze[i][j] + " "); } System.out.println(); } System.out.println("--------------------------------------------------------"); } find(x + 1, y); //下移 find(x - 1, y); //上移 find(x, y + 1); //右移 find(x, y - 1); //左移 maze[x][y] = "0"; } }

程序运行结果：

-------------------------------------------------------- 迷宫如下： 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 -------------------------------------------------------- # 0 1 0 0 0 1 0 # 0 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 # # 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 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # 0 1 0 0 0 1 0 # 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 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 # # 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 # # -------------------------------------------------------- # 0 1 0 0 0 1 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 # # -------------------------------------------------------- # # 1 0 0 0 1 0 0 # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 # # 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 # # -------------------------------------------------------- # # 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 # # -------------------------------------------------------- # # 1 0 0 0 1 0 # # 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 # # 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 # # -------------------------------------------------------- # # 1 0 0 0 1 0 # # 1 0 0 0 1 0 # 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 # # -------------------------------------------------------- 马走日