洛谷P1605 迷宫【dfs】

时间:2022-09-12 16:39:29

题目背景

迷宫 【问题描述】

给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和

终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫

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

输入样例 输出样例

【数据规模】

1≤N,M≤5

题目描述

输入输出格式

输入格式:

【输入】

第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点

坐标FX,FY。接下来T行,每行为障碍点的坐标。

输出格式:

【输出】

给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方

案总数。

输入输出样例

输入样例#1:
复制
2 2 1
1 1 2 2
1 2
输出样例#1: 复制
1

题意:

在一个n*m的格子中,有t个障碍物。

问从给定的起点走到给定的终点,每个格子只经过一次的走法有多少种。

思路:

dfs,走到终点方案数++

要注意,dfs之前要先把起点的vis标记为已访问。因为这个WA了一发。

 //#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue>
#include<map>
#include<stack>
#include<set> #define LL long long
#define ull unsigned long long
#define inf 0x3f3f3f3f using namespace std; int n, m, t;
bool barrier[][];
bool vis[][];
int stx, sty, edx, edy;
int dx[] = {, , -, };
int dy[] = {, -, , };
int ans = ; bool check(int x, int y)
{
return(x > && y > && x <= n && y <= m && !barrier[x][y] && !vis[x][y]);
} void dfs(int x, int y)
{
if(x == edx && y == edy){
ans++;
return;
}
int cnt = ;
for(int i = ; i < ; i++){
if(check(x + dx[i], y + dy[i])){
vis[x + dx[i]][y + dy[i]] = true;
dfs(x + dx[i], y + dy[i]);
vis[x + dx[i]][y + dy[i]] = false;
}
}
return;
} int main()
{
scanf("%d%d%d", &n, &m, &t);
scanf("%d%d", &stx, &sty);
scanf("%d%d", &edx, &edy);
for(int i = ; i < t; i++){
int x, y;
scanf("%d%d", &x, &y);
barrier[x][y] = true;
}
vis[stx][sty] = true;
dfs(stx, sty);
printf("%d\n", ans); return ;
}

洛谷P1605 迷宫【dfs】的更多相关文章

  1. 洛谷 P1605 迷宫

    题目链接 https://www.luogu.org/problemnew/show/P1605 题目背景 迷宫 题目描述 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 ...

  2. 洛谷—— P1605 迷宫

    P1605 迷宫 题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在 ...

  3. 洛谷P1605 迷宫 (DFS)

    题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫 中移动有上下 ...

  4. 洛谷P1605 迷宫——S&period;B&period;S&period;

    题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫 中移动有上下 ...

  5. 洛谷P1605 迷宫

    迷宫 题目链接 这道题就是一道简单的dfs计方案数qwq. 我的思路是把表初始化为1,再将障碍改为0,因为在全局定义中数组会直接初始化为0,所以就少去了对边界的特判. next数组加循环可以减少代码量 ...

  6. 洛谷P1605 迷宫 深度搜索 模板!

    题目背景 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫中移动有上下左右四种方式,每次只能移 ...

  7. (Java实现) 洛谷 P1605 迷宫

    题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫 中移动有上下 ...

  8. 洛谷 p1605 迷宫问题 详解

    题解:dfs搜索 #include <iostream> #include <algorithm> #include <cstring> #include < ...

  9. 洛谷 P1784 数独&lbrack;DFS&sol;回溯&rsqb;

    To 洛谷.1784 数独类似题:CODEVS.4966 简单数独(4*4数独) CODEVS.2924 数独挑战) 题目描述 数独是根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行 ...

随机推荐

  1. mongo里面根据对象字段的ID查询 db&period;Photo&period;find&lpar;&lbrace;&&num;39&semi;owner&period;&dollar;id&&num;39&semi;&colon;ObjectId&lpar;&&num;39&semi;xxxx&&num;39&semi;&rpar;&rcub;&rpar; &comma; 并且使用forEach循环修改查询的数据

    var ones = db.Photo.find({'owner.$id':ObjectId("5344f0dab7c58e8e098b4567")}) db.Photo.find ...

  2. dev中如何对combox下拉框设置可消除属性以及ASPxGridView中金额,数量的显示,以及总计、grid中某行值

    下拉框属性关键:IncrementalFilteringMode="StartsWith" DropDownStyle="DropDown" ASPxGridV ...

  3. go build 时报错 cc1&period;exe&colon; sorry&comma; unimplemented&colon; 64-bit mode not compiled in

    最近在玩Go win下尝试编译Go的时候遇到了下面提示(可能是gorocksdb用到了gcc) gcc也需要64位的 最后找到了个帖子: https://github.com/mattn/go-sql ...

  4. 分布式发布订阅消息系统Kafka

    高吞吐量的分布式发布订阅消息系统Kafka--安装及测试   一.Kafka概述 Kafka是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据. 这种动作(网页浏览, ...

  5. REQIMPORT-购买内部应用程序(R12&period;2&period;3)

     採购内部申请(R12.2.3) --US Program:Requisition Import Short Name:REQIMPORT Application:Purchasing Execu ...

  6. jquery中attr与prop的区别

    先从一个老生常谈的问题说起,使用jquery实现全选全不选.楼主先使用的jquery版本是 jquery-1.11.1.min.js 全选<input type="checkbox&q ...

  7. servlet运行机制、Request内置对象和服务器端跳转

    servlet运行机制: 当发送一个请求到服务器的时候,容器(Tomcat)会判断该路径属于哪一个 Servlet 进行处理,Servlet 有一个抽象父类“HttpServlet”,这个类是一个模板 ...

  8. Scala学习&lpar;四&rpar;---映射和元组

    映射和元组 摘要: 一个经典的程序员名言是:"如果只能有一种数据结构,那就用哈希表吧".哈希表或者更笼统地说映射,是最灵活多变的数据结构之一.映射是键/值对偶的集合.Scala有一个通用的叫法:元组, ...

  9. &lbrack;原&rsqb;&lbrack;osg&rsqb;&lbrack;osgEarth&rsqb;EarthManipulator关于oe漫游器的handle部分解读以及修改(仿照谷歌,修改oe漫游器中focal(视角切换)功能 续 二)

    bool EarthManipulator::handle(const osgGA::GUIEventAdapter& ea, osgGA::GUIActionAdapter& aa) ...

  10. 点击input触发弹出框的bug

    先点击第一个input建立弹出框,再点击第二个input打开弹出框,操作点击,同时触发了两个input点击事件.主要原因是建立弹出框时绑定了input1的click事件,再次触发时,又再亿次绑定了in ...