首页 > 其他分享 >洛谷题单指南-搜索-P1605 迷宫

洛谷题单指南-搜索-P1605 迷宫

时间:2024-03-06 15:45:20浏览次数:22  
标签:int 洛谷题 迷宫 nx ny && fy P1605

原题链接:https://www.luogu.com.cn/problem/P1605

题意解读:从起点走到终点的方案数,DFS可遍历所有情况。

解题思路:

在DFS过程中,有两种标记

墙:不能访问

已访问过的,不能重复访问

定义数组int a[N][N]表示迷宫,1是墙或者已访问过的,0是可以通过的。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 10;

int a[N][N];
int n, m, t;
int sx, sy, fx, fy;
int x, y;
long long ans;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void dfs(int x, int y)
{
    if(x == fx && y == fy)
    {
        ans++;
        return;
    }

    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(a[nx][ny] == 0 && nx >= 1 && nx <= n && ny >= 1 && ny <= m)
        {
            a[x][y] = 1; //这里要特别注意,要对x、y进行已访问标记
            dfs(nx, ny);
            a[x][y] = 0; //恢复以回溯
        }
    }
}

int main()
{
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;

    while(t--)
    {
        cin >> x >> y;
        a[x][y] = 1;
    }

    dfs(sx, sy);
    cout << ans;

    return 0;
}

 

标签:int,洛谷题,迷宫,nx,ny,&&,fy,P1605
From: https://www.cnblogs.com/jcwy/p/18056765

相关文章

  • 洛谷题单指南-搜索-P1433 吃奶酪
    原题链接:https://www.luogu.com.cn/problem/P1433题意解读:计算经过所有奶酪一次的总路径最短,可以采用dfs、dp等方法。解题思路:最直接的思路是DFS,暴搜所有的路径方案,计算最小距离,n最大是15,复杂度为15!≈10^12,必定会超时,先保证正确性,得到部分分:50分代码:#include<bits/stdc++.h......
  • 洛谷题单指南-搜索-P2895 [USACO08FEB] Meteor Shower S
    原题链接:https://www.luogu.com.cn/problem/P2895题意解读:所谓安全格子,就是在所有流星坠落之后,没有被烧焦的格子,要计算从起点到这些格子任一一个的最短路径,BFS可以解决。解题思路:1、读取数据,先把所有流星坠落点以及周围被烧焦的格子进行标记,得到安全格子2、从起点开始BFS,每走......
  • 洛谷题单指南-搜索-P1135 奇怪的电梯
    原题链接:https://www.luogu.com.cn/problem/P1135题意解读:计算A到B至少要按几次电梯,本质上就是求A到B的最短路径,可以通过BFS解决。解题思路:位于每一层,有两种选择:向上、向下BFS搜索直接从A找到B,每扩展一层,层数+1,层数即按电梯次数100分代码:#include<bits/stdc++.h>usingnam......
  • 题解 P10220【[省选联考 2024] 迷宫守卫】
    \(\text{Link}\)葬送了我2024省选的一题。题意有一颗深度为\(n+1\)的完全二叉树,其叶子上依次标有一个长为\(2^n\)排列\(a\),非叶结点有选择代价\(b_i\)。Alice、Bob两人进行游戏。Alice可以选择一些选择代价和不超过\(m\)的非叶结点,此后Bob会从根开始深度优先搜索......
  • 洛谷题单指南-搜索-P1443 马的遍历
    原题链接:https://www.luogu.com.cn/problem/P1443题意解读:无论是国际象棋还是中国象棋,马的活动范围都是一样的:只不过国际象棋棋子是在格子中,中国象棋棋子是在交点,坐标的变化方式是一样的,根据此活动范围,计算马到达每一个点的最短路径。解题思路:根据马的活动范围,在棋盘内进行B......
  • 洛谷题单指南-搜索-P2392 kkksc03考前临时抱佛脚
    原题链接:https://www.luogu.com.cn/problem/P2392解题思路:参考https://www.cnblogs.com/jcwy/p/18003097前面已经给出了二进制法的代码,这里给出DFS的代码100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=25;ints1,s2,s3,s4;inta[N],b[N],c[......
  • 洛谷题单指南-搜索-P1219 [USACO1.5] 八皇后 Checker Challenge
    原题链接:https://www.luogu.com.cn/problem/P1219题意解读:八皇后,经典回溯问题。解题思路:逐行摆放棋子,关键在于如何快速判断行、列、正斜(左上到右下)、反斜(右上到左下)方向没有已放其他棋子1、由于逐行摆放,因此行不需要判断通过一个boolcol[N]数组即可判断列上是否已摆放其他棋......
  • 洛谷题单指南-二分查找与二分答案-P3743 kotori的设备
    原题链接:https://www.luogu.com.cn/problem/P3743题意解读:设备使用的时间越久,需要充电的总时间也越多,具备单调性,根据使用的时间,计算需要充电的时间,如果充电总时间<=使用的时间,说明有电量还能富余,使用时间还可以更多,因此只需对使用时间进行二分即可。解题思路:给定设备使用的时间......
  • P10220 [省选联考 2024] 迷宫守卫 题解
    说一下自己赛时做法。赛时会了,但没能调出来,几乎确定进不去队了,留下这篇题解作为这次比赛的记录吧。称激活守卫为打开开关。首先考虑,如果确定所有开关的情况,Bob有一个简单的贪心做法:当走到一个点时,递归其左右子树并得到两个序列,若右子树的对应序列的小于左子树的对应序列,则右边......
  • P10220 [省选联考 2024] 迷宫守卫
    二分+贪心+DP。跟D1T2思路有点类似,反正很简单。复杂度大约是\({\rmO}(n^22^n)\)。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+5;constllinf=1e18;intT,n,q[N];llK,w[N];vector<int>Q;lldp(into,intd,in......