题目背景
迷宫 【问题描述】
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和
终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫
中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
输入样例 输出样例
【数据规模】
1≤N,M≤5
题目描述
输入输出格式
输入格式:
【输入】
第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点
坐标FX,FY。接下来T行,每行为障碍点的坐标。
输出格式:
【输出】
给定起点坐标和终点坐标,问每个方格最多经过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】的更多相关文章
-
洛谷 P1605 迷宫
题目链接 https://www.luogu.org/problemnew/show/P1605 题目背景 迷宫 题目描述 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 ...
-
洛谷—— P1605 迷宫
P1605 迷宫 题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在 ...
-
洛谷P1605 迷宫 (DFS)
题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫 中移动有上下 ...
-
洛谷P1605 迷宫——S.B.S.
题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫 中移动有上下 ...
-
洛谷P1605 迷宫
迷宫 题目链接 这道题就是一道简单的dfs计方案数qwq. 我的思路是把表初始化为1,再将障碍改为0,因为在全局定义中数组会直接初始化为0,所以就少去了对边界的特判. next数组加循环可以减少代码量 ...
-
洛谷P1605 迷宫 深度搜索 模板!
题目背景 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫中移动有上下左右四种方式,每次只能移 ...
-
(Java实现) 洛谷 P1605 迷宫
题目背景 迷宫 [问题描述] 给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过.给定起点坐标和 终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案.在迷宫 中移动有上下 ...
-
洛谷 p1605 迷宫问题 详解
题解:dfs搜索 #include <iostream> #include <algorithm> #include <cstring> #include < ...
-
洛谷 P1784 数独[DFS/回溯]
To 洛谷.1784 数独类似题:CODEVS.4966 简单数独(4*4数独) CODEVS.2924 数独挑战) 题目描述 数独是根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行 ...
随机推荐
-
mongo里面根据对象字段的ID查询 db.Photo.find({&#39;owner.$id&#39;:ObjectId(&#39;xxxx&#39;)}) , 并且使用forEach循环修改查询的数据
var ones = db.Photo.find({'owner.$id':ObjectId("5344f0dab7c58e8e098b4567")}) db.Photo.find ...
-
dev中如何对combox下拉框设置可消除属性以及ASPxGridView中金额,数量的显示,以及总计、grid中某行值
下拉框属性关键:IncrementalFilteringMode="StartsWith" DropDownStyle="DropDown" ASPxGridV ...
-
go build 时报错 cc1.exe: sorry, unimplemented: 64-bit mode not compiled in
最近在玩Go win下尝试编译Go的时候遇到了下面提示(可能是gorocksdb用到了gcc) gcc也需要64位的 最后找到了个帖子: https://github.com/mattn/go-sql ...
-
分布式发布订阅消息系统Kafka
高吞吐量的分布式发布订阅消息系统Kafka--安装及测试 一.Kafka概述 Kafka是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据. 这种动作(网页浏览, ...
-
REQIMPORT-购买内部应用程序(R12.2.3)
採购内部申请(R12.2.3) --US Program:Requisition Import Short Name:REQIMPORT Application:Purchasing Execu ...
-
jquery中attr与prop的区别
先从一个老生常谈的问题说起,使用jquery实现全选全不选.楼主先使用的jquery版本是 jquery-1.11.1.min.js 全选<input type="checkbox&q ...
-
servlet运行机制、Request内置对象和服务器端跳转
servlet运行机制: 当发送一个请求到服务器的时候,容器(Tomcat)会判断该路径属于哪一个 Servlet 进行处理,Servlet 有一个抽象父类“HttpServlet”,这个类是一个模板 ...
-
Scala学习(四)---映射和元组
映射和元组 摘要: 一个经典的程序员名言是:"如果只能有一种数据结构,那就用哈希表吧".哈希表或者更笼统地说映射,是最灵活多变的数据结构之一.映射是键/值对偶的集合.Scala有一个通用的叫法:元组, ...
-
[原][osg][osgEarth]EarthManipulator关于oe漫游器的handle部分解读以及修改(仿照谷歌,修改oe漫游器中focal(视角切换)功能 续 二)
bool EarthManipulator::handle(const osgGA::GUIEventAdapter& ea, osgGA::GUIActionAdapter& aa) ...
-
点击input触发弹出框的bug
先点击第一个input建立弹出框,再点击第二个input打开弹出框,操作点击,同时触发了两个input点击事件.主要原因是建立弹出框时绑定了input1的click事件,再次触发时,又再亿次绑定了in ...