DFS题单以及模板汇总

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

• P1605 迷宫

迷宫

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

提示

对于 $100\%$ 的数据，$1\le N,M\le 5$，$1\le T\le 10$，$1\le SX,FX\le n$，$1\le SY,FY\le 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;
    }

}