文档章节

洛谷P1605 迷宫 (DFS)

o
 osc_n6euf5h6
发布于 2019/03/19 20:41
字数 485
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目背景

迷宫 【问题描述】

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

计数方式:能到终点就加一 但是走过的地方需要标记一下
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 char a[35][35];
 6 int n,m,t;
 7 int res=0;
 8 int dx[4]={1,-1,0,0};
 9 int dy[4]={0,0,1,-1};
10 int sx,sy,ex,ey;
11 void dfs(int x,int y)
12 {
13     if(x==ex-1&&y==ey-1) {
14         res++;
15         return;
16     }
17     for(int i=0;i<4;i++){
18         int nx=x+dx[i],ny=y+dy[i];
19         if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]=='.'){
20             a[x][y]='#';
21             dfs(nx,ny);
22             a[x][y]='.';
23         }
24     }
25     return ;
26 }
27 int main()
28 {
29     while(cin>>m>>n>>t){
30         for(int i=0;i<n;i++){
31             for(int j=0;j<m;j++){
32                 a[i][j]='.';
33             }
34         } 
35         cin>>sx>>sy>>ex>>ey;
36         while(t--){
37             int x,y;
38             cin>>x>>y;
39             a[x-1][y-1]='#';
40         }
41         a[sx-1][sy-1]='#';
42         dfs(sx-1,sy-1);
43         cout<<res<<endl;
44     } 
45     return 0;
46 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【洛谷】普及练习场 深度优先搜索【易】

P1219 八皇后 题目大意: 给出一个n*n的正方形棋盘,在上棋盘上放下n个皇后,要求每个皇后所在的行,列,两条对角线上没有其他皇后,输出前三种解法(按字典序排,输出结果从上到下用列号表示...

osc_28hs2gg6
2019/05/09
2
0
计蒜客 T1595 迷宫(一)题解

hi,大家好,我是Loony lovegood.今天突发奇想写了一篇题解 先推荐个oj //不是做广告 计蒜客 最好的oj 洛谷 好了,废话不多说了.以下是正文. 没看题的小伙伴戳这里 T1595题目 题目主要描述 两个...

osc_9oidllr2
07/10
2
0
基础算法·深度优先搜索

祝食用愉快XD 题目链接 (是一道胡乱出的题)U56815 来走迷宫鸭! 解题思路 深度优先搜索,如果能不碰墙地到达右下角的出口,就把旗子立起来表示找到了出口。什么?你没听过深度优先搜索没事...

osc_994n5tsc
2018/12/18
2
0
Loony的dfs推荐题目

hi,大家好,你们的Loony又回来了!今天不打算写题解,那就来推荐一些dfs的题目吧!纯属觉得贴超链接好玩 (后面附有难度指数哦) 切记,只是推荐题目(只本人觉得好的,典型的题哦)不代表网站...

osc_7co5s4uj
07/11
4
0
迷宫寻路问题全解

1、深度优先搜索(DFS)+回溯 最基本的板子: void DFS(int x,int y){ } } 适用类型①:求可行解数量 https://www.luogu.org/problemnew/show/P1605 #include <iostream>using nam......

osc_tg4e471h
2019/04/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux系统检查用户账户到期时间

如果你在 Linux 上启用了密码策略。密码必须在到期前进行更改,并且登录到系统时会收到通知。如果你很少使用自己的帐户,那么可能由于密码过期而被锁定。在许多情况下,这可能会在无需密码登...

老孟的Linux私房菜
31分钟前
13
0
关于南京哪里有开餐饮费发票?

关于南京哪里有开餐饮费发票?聚焦餐饮行业,谈话〖18 7一電一7 5 3 8一徴一3331〗研究院昨发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元.随着餐饮行业的快速...

点击fojewio
今天
7
0
android studio 4.0 打开DDMS

1、先找到AndroidStudio配置的SDK路径; 2、在SDK的/tools/路径下有个monitor.bat 的批处理文件; 3、鼠标连续点击两下monitor.bat这个批处理文件,在屏幕上会打开一个类似CMD的命令行中输入...

chenhongjiang
今天
10
0
如何在Android中使用SharedPreferences来存储,获取和编辑值

问题: Closed . 已关闭 。 This question needs to be more focused. 这个问题需要更加集中。 It is not currently accepting answers. 它当前不接受答案。 Learn more . 了解更多 。 Want...

fyin1314
今天
6
0
【JDK1.8】LinkedList源码分析

LinkedList的特性 LinkedList内部使用双向链表作为存储结构,LinkedList可以理解为链表的扩展对象,封装了常用的和非常用的操作链表的方法。以及在通过索引获取元素时的简单优化,通常Linke...

XuePeng77
今天
36
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部