DFS题单以及模板汇总

此文章是为了记录自己学习DFS算法以及记录写过的DFS题单汇总，持续补充

• P1605 迷宫

迷宫

题目描述

给定一个 N × M N \times M N×M 方格的迷宫，迷宫里有 T T T 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 N , M , T N,M,T N,M,T，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY， S X , S Y SX,SY SX,SY 代表起点坐标， F X , F Y FX,FY FX,FY 代表终点坐标。

接下来 T T T 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

提示

对于 100 % 100\% 100% 的数据， 1 ≤ N , M ≤ 5 1 \le N,M \le 5 1≤N,M≤5， 1 ≤ T ≤ 10 1 \le T \le 10 1≤T≤10， 1 ≤ S X , F X ≤ n 1 \le SX,FX \le n 1≤SX,FX≤n， 1 ≤ S Y , F Y ≤ m 1 \le SY,FY \le m 1≤SY,FY≤m。

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;
    }

}