信息学奥赛一本通T1255-迷宫问题-题解（Java代码）详细思路注释

解题思路:
用dfs，向4个方向疯狂试探，如果可以走就将走过的地方改为2，用于后面记录走过的路径，并且也要记录步数，用于计算最短路。
注意事项:
走的方向一定要注意，因为是要输出路径的，所以dfs试探走的方向一定要和样例里走的方向一样，这里很坑，因为题目样例看不出方向这个坑，也是提交出现错误以后看了样例才发现方向一定要先向下走才行，如果是计算步数就不需要这么严格。
参考代码:

import java.util.Scanner;


public class e10_11 {

	/**
	 * @param args
	 */
	static int [][]fx={{1,0},{0,1},{-1,0},{0,-1}};//这里的方向很重要，一定要先向下走，因为这里是输出走过的路径，输出的必须要和样例答案的顺序一样，如果是输出走过的步数就不需要这么严格，想从哪个方向先走都可
	static int min=999999;
	static String xs="";
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int [][]sz=new int[5][5];
		for (int i = 0; i < sz.length; i++) {
			for (int j = 0; j < sz[i].length; j++) {
				sz[i][j]=scanner.nextInt();
			}
		}
		sz[0][0]=2;//将起点变成走过
		dfs(0, 0, sz,0);
		
		//截取走过的路径的坐标字符串
		while (true) {
			int x=xs.indexOf(".");//找到.的下标
			System.out.println(xs.substring(0, x));//截取输出第一个字符到.的字符串表示一个坐标
			//判断是否进行到最后了
			if (x==xs.length()-1) {
				break;
			}
			//这里是将截取输出过的字符串去掉，只保留后面没有截取的字符串
			xs=xs.substring(x+1, xs.length());
		}
	}
	
	public static void dfs(int i,int j,int [][]sz,int count) {
		if (i==4&&j==4) {
			//如果到达终点就用字符串将走过的坐标存起来
			String zfc="";
			for (int k = 0; k < sz.length; k++) {
				for (int l = 0; l < sz[k].length; l++) {
					if (sz[k][l]==2) {
						zfc+="("+k+", "+l+").";
					}
				}
			}
			//这里是判断走的步数是不是最少的，如果是最少的就将存着坐标的字符串赋值给全局变量xs用于在main中截取显示
			if (count<min) {
				min=count;
				xs=zfc;
			}
			return;
		}
		//向四个方向走（疯狂试探）
		for (int k = 0; k < 4; k++) {
			int h=i+fx[k][0];
			int l=j+fx[k][1];
			if (h>=0&&h<5&&l>=0&&l<5&&sz[h][l]==0) {
				sz[h][l]=2;//将走过的地方变成2，后面好记录走过的路的坐标
				dfs(h, l, sz,count+1);
				sz[h][l]=0;//回溯
			}
		}
	}

}