首页 > 其他分享 >深度优先搜索 洛谷P1605迷宫

深度优先搜索 洛谷P1605迷宫

时间:2024-05-22 18:41:39浏览次数:29  
标签:le 洛谷 int 迷宫 FX 坐标 P1605 起点

深度优先搜索

洛谷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$。
可先看我的另一个博客

题目简单直接附代码了

#include<bits/stdc++.h>
using namespace std;
int n, m, t;
int x_0, y_0, xfinal, yfinal, ans = 0, flag[10][10] = {0};
int d[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}};
bool check(int x, int y) {
    if(x > n || y > m || x <= 0 || y <= 0) return false;
    if(flag[x][y]) return false;
    return true;
}
void dfs(int x, int y) {
    if(x == xfinal && y == yfinal) ans++;
    else {
        
        for(int i = 0; i < 4; i++) {
            if(check(x+d[i][0], y+d[i][1])) {
                flag[x][y] = 1;
                dfs(x+d[i][0], y+d[i][1]);
                flag[x][y] = 0;
            }
        }
    }
    
}
int main() {
    cin >> n >> m >> t;
    cin >> x_0 >> y_0 >> xfinal >> yfinal;
    for(int i = 0; i < t; i++) {
        int x, y;
        cin >> x >> y;
        flag[x][y] = 1;
    }
    dfs(x_0, y_0);
    cout << ans;
    system("pause");
}

标签:le,洛谷,int,迷宫,FX,坐标,P1605,起点
From: https://www.cnblogs.com/rjxq/p/18206881

相关文章

  • 广度优先搜索 洛谷P2895Meteor Shower S
    广度优先搜索洛谷P2895[USACO08FEB]MeteorShowerS题面翻译题目描述贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。如果将牧场放入一个直角坐标系中,贝茜......
  • 二分答案 洛谷P3853路标设置
    这个题思路和洛谷P2440有点像,建议先看P2440这个题,较简单。[TJOI2007]路标设置题目背景B市和T市之间有一条长长的高速公路,这条公路的某些地方设有路标,但是大家都感觉路标设得太少了,相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题,我们把公路上相邻路标的最......
  • 广度优先搜索 洛谷P1443马的遍历(bfs超时问题)
    广度优先搜索洛谷P1443这里先介绍一下广度优先搜索:广度优先搜索就是先将第一步可能的步骤全部记录,遍历过后,再将由第一步到达的第二步全部记录并遍历,直到最后全部遍历。而此题要求我们求得最少步数,广度优先就能够达到最少步数的要求,因为广度优先是先通过搜索所有可能的第n步才......
  • 深度优先搜索 洛谷P1219八皇后
    深度优先搜索洛谷P1219这是一道经典的深度优先搜索问题,深度优先搜索可用以下模板:voiddfs(intdepth){ if(达到边界){ 记录解 } for(枚举在depth这一深度,能够使用的解){ if(解可行){ 记录解(记录已经被使用) dfs(depth+1) 恢复解(恢复原状) } }}题目要求我们......
  • 二分答案 洛谷2440木材加工
    二分答案题目详见洛谷P2440木材加工分享一下自己新学习的二分答案的方法,开始可能有点奇怪为啥这样能做,但其实思路很简单。起始思路题目要求我们求最大的分解长度,所以我(们)最开始想的肯定是从大到小(求最大值)枚举答案,看看是否满足,满足不了就加1。但这样暴力肯定是会超时的,那我们......
  • 洛谷 P4383 [八省联考 2018] 林克卡特树
    原题等价于在树上选出\(k+1\)条不相交链,最大化边权和。树形DP。设\(f_{u,k,0/1/2}\)表示在\(u\)的子树中选了\(k\)条链,\(u\)的度数为\(0,1,2\)的最大边权和。注意到状态里缺了链退化为单个点的情况,可以把它放到\(f_{u,k,2}\)中(相当于自环)。转移时分讨一......
  • 洛谷 P10512 序列合并
    哭死,比赛的时候完全想歪了,想的是考虑一次合并能造成多大的贡献,按照贡献排序然后合并。这样做只能考虑局部造成的贡献,然而最后算的时候要考虑整体,所以并不是很对。正着想没有思路就可以倒着想,考虑枚举答案。合并k次,意味着最后是n-k个数。经典从二进制高位到低位考虑,考虑这一位(假......
  • 【Python】强化学习SARSA走迷宫
    之前有实现Q-Learning走迷宫,本篇实现SARSA走迷宫。Q-Learning是一种off-policy算法,当前步采取的决策action不直接作用于环境生成下一次state,而是选择最优的奖励来更新Q表。更新公式:SARSA是一种on-policy算法,当前步采取的策略action既直接作用于环境生成新的state,也用来更新Q表......
  • Solution -「洛谷 P8477」 「GLR-R3」春分 下界证明?!
      前情提要:在「洛谷P8477」「GLR-R3」春分中,我们给出了\(\frac{7}{6}n\pm\mathcalO(1)\)的解法,但没能给出相关的下界证明。现在我们尝试给出一个未完全完成的下界证明。  为方便描述,我们综合链接中题意和某个“通俗”的题意,称隔板为“板”,称溶液为“人”。  这个......
  • 「杂题乱刷」洛谷 P10467
    题目链接P10467[CCC2007]SnowflakeSnowSnowflakes解题思路字符串哈希板子题。思路就是我们给每个数列的所有排列都哈希一个值,然后判断是否有不同的数列的哈希值相同,如果有,就输出Twinsnowflakesfound.,否则就输出Notwosnowflakesarealike.。参考代码这里使用双哈......