文档章节

复试训练——搜索——深度优先遍历(DFS)

wudangt
 wudangt
发布于 2017/02/10 20:54
字数 579
阅读 1
收藏 0

题目1461:Tempter of the bone

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:2230

解决:779

题目描述:

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

输入:

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter; 
'S': the start point of the doggie; 
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed. 

输出:

For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.

样例输入:

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

样例输出:

NO
YES

提示:

 用scanf读取输入。

代码:

#include <stdio.h>
char maze[8][8];
int n,m,t;
bool success;
int go[][2]={
	1,0,
	-1,0,
	0,1,
	0,-1
};
void DFS(int x,int y,int time){
	int i;
	for(i=0;i<4;i++){
		int nx=go[i][0]+x;
		int ny=go[i][1]+y;
		if(nx<1||nx>n||ny<1||ny>m) continue;
		if(maze[nx][ny]=='X')continue;
		if(maze[nx][ny]=='D'){
		if(time+1==t){
			success=true;
			return;
		}
		else continue;
		}
		maze[nx][ny]='X';
	    DFS(nx,ny,time+1);
		maze[nx][ny]='.';
     	if(success) return;
	}	
}
int main(){
	while(scanf("%d%d%d",&n,&m,&t)!=EOF){
		if(n==0&&m==0&&t==0) break;
		int i;
		for(i=1;i<=n;i++){
			scanf("%s",maze[i]+1);

		}
		success=false;
		int sx,sy;
		for(i=1;i<=n;i++){
			int j;
			for(j=1;j<=m;j++){
				if(maze[i][j]=='D'){
				sx=i;
				sy=j;
				}
			}
		}
		for(i=1;i<=n;i++){
			int j;
			for(j=1;j<=m;j++){
				if(maze[i][j]=='S'&&(i+j)%2==((sx+sy)%2+t%2)%2){
					maze[i][j]='X';
					DFS(i,j,0);
				}
			}
		}
		puts(success==true ? "YES":"NO");
	}
	return 0;
}

 

© 著作权归作者所有

wudangt
粉丝 0
博文 46
码字总数 23847
作品 0
黄浦
其他
私信 提问
考研复试系列——第四节 深度优先搜索

考研复试系列——第四节 深度优先搜索 前言 dfs:if(判断条件) //在这里进行递归的退出return;for(遍历内容) //进行遍历,例如图中访问每一个满足某一条件的节点{if(判断是否访问过以及其他题...

cassiepython
2017/03/01
0
0
python实现二叉树的遍历以及基本操作

主要内容: 二叉树遍历(先序、中序、后序、宽度优先遍历)的迭代实现和递归实现; 二叉树的深度,二叉树到叶子节点的所有路径; 首先,先定义二叉树类(python3),代码如下:

pandaWaKaKa
06/25
0
0
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0
漫画:深度优先遍历 和 广度优先遍历

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/bjweimengshu/article/details/88801664

程序员小灰
03/25
0
0
数据结构与算法--图论之寻找连通分量、强连通分量

数据结构与算法--图论之寻找连通分量、强连通分量 寻找无向图的连通分量 使用深度优先搜索可以很简单地找出一幅图的所有连通分量,回忆连通图的概念:如果从任意顶点都存在一条路径达到任意一...

sunhaiyu
2017/11/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
16
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
18
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部