DFS题单以及模板汇总

简介: DFS题单以及模板汇总

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

迷宫

题目描述

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

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

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

输入格式

image.png

输出格式

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

样例

样例输入

2 2 1
1 1 2 2
1 2

样例输出

1

提示

image.png

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


相关文章
|
机器学习/深度学习 物联网 开发者
秒级生图,SDXL-turbo、LCM-SDXL魔搭社区最佳实践
最近一个月,快速生图成为文生图领域的热点,其中比较典型的两种方式的代表模型分别为SDXL-turbo 和 LCM-SDXL。
|
人工智能
基于qwen2和qwenvl的自动批改作业应用!
针对作业批改中常见的问题,如低质量作业、大量简单作业耗时、需初筛异常作业等,开发了一款自动批改作业的应用。该应用通过备份作业文件、获取文档内容、利用AI生成评语,并保存关键信息与日志,简化了教师的工作流程,提高了效率。应用设计简洁,易于扩展,支持图片转文字处理,适合教育场景使用。
4091 1
基于qwen2和qwenvl的自动批改作业应用!
|
存储 负载均衡 算法
p2p的文件系统
p2p的文件系统
454 4
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
10458 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
|
安全 数据安全/隐私保护 开发者
【Python】 已解决:ERROR: Could not install packages due to an OSError: [WinError 5] 拒绝访问。: ‘e:\anaconda\i
【Python】 已解决:ERROR: Could not install packages due to an OSError: [WinError 5] 拒绝访问。: ‘e:\anaconda\i
5075 11
【Python】 已解决:ERROR: Could not install packages due to an OSError: [WinError 5] 拒绝访问。: ‘e:\anaconda\i
|
NoSQL MongoDB Windows
MongoDB 读写分离——Windows MongoDB 副本集配置
MongoDB 读写分离——Windows MongoDB 副本集配置
446 0
|
监控 数据挖掘 UED
ROI
【5月更文挑战第16天】ROI
4653 4
|
机器学习/深度学习 编解码 算法
ICCV 2023 | SPIN:轻量级图像超分辨率与超像素令牌交互
ICCV 2023 | SPIN:轻量级图像超分辨率与超像素令牌交互
379 1
|
存储 缓存 网络协议
CDNJS/UNPKG/JSDelivr 太慢用不了,换成这些国内高速镜像
npm cdn, cdnjs, unpkg, jsdelivr, zstatic, zstatic.net, s4.zstatic.net
20068 4
|
Kubernetes 安全 物联网
大规模 IoT 边缘容器集群管理的几种架构 -3-Portainer
大规模 IoT 边缘容器集群管理的几种架构 -3-Portainer