洛谷P1605:迷宫(DFS)

时间:2022-09-12 16:30:13

题目背景

迷宫 【问题描述】

给定一个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

AC代码

注意要对起点也进行标记,否则只能拿到70分

不对起点进行标记的被卡的数据:

2 2 0
1 1 1 2
#include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn=1e6+10;
using namespace std;
int mp[10][10];
int vis[100][100];
int dis[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,t;
int ans;
void dfs(int x,int y,int fx,int fy)
{
vis[x][y]=1;
if(x==fx&&y==fy)
ans++;
for(int i=0;i<4;i++)
{
int dx=x+dis[i][0];
int dy=y+dis[i][1];
if(!vis[dx][dy]&&!mp[dx][dy]&&dx<=n&&dx>0&&dy<=m&&dy>0)
{
dfs(dx,dy,fx,fy);
vis[dx][dy]=0;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>t;
int sx,sy,fx,fy;
cin>>sx>>sy>>fx>>fy;
int zx,zy;
for(int i=0;i<t;i++)
{
cin>>zx>>zy;
mp[zx][zy]=1;
}
dfs(sx,sy,fx,fy);
cout<<ans<<endl;
return 0;
}

洛谷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 迷宫【dfs】

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

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

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

  6. 洛谷P1605 迷宫

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

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

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

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

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

  9. 洛谷 p1605 迷宫问题 详解

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

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

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

随机推荐

  1. 基于改进人工蜂群算法的K均值聚类算法(附MATLAB版源代码)

    其实一直以来也没有准备在园子里发这样的文章,相对来说,算法改进放在园子里还是会稍稍显得格格不入.但是最近邮箱收到的几封邮件让我觉得有必要通过我的博客把过去做过的东西分享出去更给更多需要的人.从论文刊登 ...

  2. Model View Controller

    On the iPhone or iPod touch, a modal view controller takes over the entire screen. This is the defau ...

  3. C&plus;&plus; 顺序容器

    <C++ Primer 4th>读书笔记 顺序容器内的元素按其位置存储和访问.容器类共享公共的接口,每种容器类型提供一组不同的时间和功能折衷方案.通常不需要修改代码,只需改变类型声明,用一 ...

  4. 树形DP(Holiday&&num;39&semi;s Accommodation HDU4118)

    题意:有n间房子,之间有n-1条道路连接,每个房间里住着一个人,这n个人都想到其他房间居住,并且每个房间不能有两个人,问所有人的路径之和最大是多少? 分析:对于每条边来说,经过改边的人由该边两端元素个 ...

  5. Solution for When browse http&colon;&sol;&sol;xxx&sol;ReportServer Show Error &lpar;rsAccessDenied&rpar;

    Issue: Reporting Services Error The permissions granted to user 'IDEAAM\William' are insufficient fo ...

  6. Python 2&period;7&period;3的文件编码问题,print在控制台下面中文乱码问题,以及推荐做法

    情况:文件乱码,在cmd上输出print也乱码.解决方案:统一为gbk的简体中文编码方式.步骤如下: 1.每个py文件使用[简体中文(GB2312)- 代码页 936]格式保存,行尾为[Windows ...

  7. 万人迷”微信小程序似乎开始掉粉 为什么呢?

    "万人迷"微信小程序最近似乎开始掉粉. 距离1月9日小程序上线已有一周,相比浓烈的讨论气氛,用户的使用热情逐步降低,而部分公司开始撤离小程序. 其中,逻辑思维旗下产品"得 ...

  8. JavaScript设计模式之策略模式

    所谓"条条道路通罗马",在现实中,为达到某种目的往往不是只有一种方法.比如挣钱养家:可以做点小生意,可以打分工,甚至还可以是偷.抢.赌等等各种手段.在程序语言设计中,也会遇到这种类 ...

  9. lua&lowbar;cocos精灵的不断闪动

    一.   刚开始使用 local blink = cc.Blink:create(1, 10)   sprite:runAction(blink)                            ...

  10. Delphi各种Socket组件的模式和模型

    Delphi各种Socket组件的模式和模型 Delphi的大多数书籍里面都没有提到delphi的各种socket通信组件的模式和模型,有的书只讲解了windows的socket模式和模型,并没有归纳 ...