此文章是为了记录自己学习DFS算法以及记录写过的DFS题单汇总，持续补充
迷宫
题目描述
给定一个N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
输出格式
输出从起点坐标到终点坐标的方案总数。
样例
样例输入
2 2 1 1 1 2 2 1 2
样例输出
1
提示
AC代码：
import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { static int n; static int m; static int N = 10; static int T; static int[][] arr = new int[N][N]; static boolean[][] vis = new boolean[N][N]; static int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}}; static int res = 0; static int x0; static int y0; static int x; static int y; public static void main(String[] args) throws IOException { Read read = new Read(); n = read.nextInt(); m = read.nextInt(); T = read.nextInt(); // (x0,y0) -> 起始点坐标 // (x,y) -> 终点坐标 x0 = read.nextInt(); y0 = read.nextInt(); x = read.nextInt(); y = read.nextInt(); for (int i = 1 ; i <= n; i++) { for (int j = 1; j <= m; j++) { // 赋予默认值1 arr[i][j] = 1; } } for (int k = 1 ; k <= T; k++) { // 标记障碍物为0 int a1 = read.nextInt(); int a2 = read.nextInt(); arr[a1][a2] = 0; } dfs(x0,y0); System.out.println(res); } public static void dfs(int i,int j) { // 如果到达终点退出循环 if (i == x && j == y) { res++; return; } else { // 针对(i,j)坐标每次进行上下左右的探索 for (int k = 0 ; k < 4; k++) { int dx = i + dir[k][0]; int dy = j + dir[k][1]; // 如果当前坐标(dx,dy)没有被访问过，且(dx,dy)是非障碍物点 if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && arr[dx][dy] == 1 && !vis[dx][dy]) { // 标记(i,j)已经遍历过 vis[i][j] = true; dfs(dx, dy); // 还原(i,j) vis[i][j] = false; } } } } } class Read { StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in)); public int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } public double nextDouble() throws IOException { st.nextToken(); return st.nval; } public String nextString() throws IOException { st.nextToken(); return st.sval; } }
