DFS解法，典型迷宫类问题

我在做笔记！！！

理解的属于前面大佬们的代码

思路：

    1、找到A点的坐标，标记下来，储存4四种走法类型，申请一个boolean类型，判段方格是否走过，避免死循环

    2、循环4种类型，判段是否超出边界，如果没有超出边界，标记为true，继续DFS下一个坐标，回溯

    3、如果找到了B点，判段当前count步数与ans中储存的最小步数谁更小，储存更小的

    4、如果没有找到，ans即为原设定值，返回-1，找到了返回ans

DFS类型基本思路

    1、初始点出发

    2、遍历每种情况，标记当前点为true

    3、回溯

    4、判段终点

注意事项:

参考代码:

import java.io.*;

public class Main {
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	//记录A坐标
	static int a,b;
	//储存行走方向的数组
	static int dir[][] = {{1,0},{0,1},{-1,0},{0,-1}};
	static int ans=10000; //最小步数
	//题目最大给出范围100
	static char[][] maze=new char[101][101];
	static boolean[][] iswalked=new boolean[101][101];
	static int n;
	public static void main(String[] args) throws NumberFormatException, IOException {
		n=Integer.parseInt(bf.readLine());//方阵大小
		for(int i=0;i<n;i++) {
			String[] temp=bf.readLine().split(" ");
			for(int j=0;j<n;j++) {
				maze[i][j]=temp[j].charAt(0);
				if(maze[i][j]=='A') {
					a=i;
					b=j;
				}
			}
		}
		dfs(a,b,'A',0);
		if(ans!=10000) {
			pw.print(ans);
		}else {
			//走不到
			pw.print("-1");
		}
		pw.flush();
	}
	
	public static void dfs(int x,int y,char laststatus,int count) {
		if(maze[x][y]=='B') {
			ans=Math.min(ans, count);
			return;
		}
		//遍历上下左右四种情况
		for(int i=0;i<4;i++) {
			int tempx=x+dir[i][0];
			int tempy=y+dir[i][1];
			if(tempx>=0&&tempy>=0&&tempx<n&&tempy<n&&maze[x][y]!=maze[tempx][tempy]&&!iswalked[tempx][tempy]) {
				iswalked[tempx][tempy]=true;
				dfs(tempx,tempy,laststatus,count+1);
				//回溯
				iswalked[tempx][tempy]=false;
			}
		}
	}
}