【Java||牛客】DFS应用迷宫问题

step by step.

题目：

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2 \le n,m \le 10 \2≤n,m≤10  ， 输入的内容只包含 0 \le val \le 1 \0≤val≤1 

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

示例1

输入：

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

复制输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

思路：

按照DFS，看能走的路，能走则继续走，但是要注意回溯。

注意：！！！

1. 边界一定要i和j都检测，这里的j的范围是arr[0]的长度要注意

2. 要设置全局变量static StringBuffer()，如果不设置的话，最后输出时遍历数组arr[i][j]==2则赎出=>不正确！！因为遍历顺序和迷宫路径顺序不是同一个逻辑，不能单纯从左到右从上到下来遍历出路，不可行！！这里疑惑了好久，后来测试dfs完的数组确实路径是对的，但是赎出的坐标不正确，可能就是这个原因

3. 要把走过的路设置成2，因为有可能要回溯

4. 一定要回溯

5.细心，边界的情况，不只是越大界，还有可能i<0，因为dfs会往回走

代码

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static StringBuffer sb = new StringBuffer();public static boolean dfs(int[][] arr,int i,int j,String res){//判断边界//走出迷宫if(i>arr.length-1||j>arr[0].length-1||i<0||j<0) return false;if(i==arr.length-1&&j==arr[0].length-1){//System.out.println("return true");sb.append(res);sb.append("("+i+","+j+")");arr[i][j]=2;return true;}//if(arr[i][j]==0){//可走arr[i][j]=2;//标记if(dfs(arr,i-1,j,res+"("+i+","+j+")\n")) return true;if(dfs(arr,i+1,j,res+"("+i+","+j+")\n")) return true;if(dfs(arr,i,j-1,res+"("+i+","+j+")\n")) return true;if(dfs(arr,i,j+1,res+"("+i+","+j+")\n")) return true;arr[i][j] = 0;//System.out.println("return true2");}return false;}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint[][] arr = new int[in.nextInt()][in.nextInt()];for(int i=0;i<arr.length;i++){for(int j=0;j<arr[0].length;j++){arr[i][j] = in.nextInt();}}dfs(arr,0,0,"");System.out.println(sb.toString());/*for(int i=0;i<arr.length;i++){for(int j=0;j<arr[0].length;j++){if(arr[i][j] == 2){System.out.println("("+i+","+j+")");//System.out.print("2 ");}}//System.out.println();}*/}}
}