Kolstad and Schrijvers
Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two "exits" for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect' maze: you can find a way out of the maze from any point inside it.
Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the `worst' point in the maze (the point that is `farther' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move "out" of the maze.
Here's what one particular W=5, H=3 maze looks like:
+-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+
Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.
PROGRAM NAME: maze1
INPUT FORMAT
Line 1: | W and H, space separated |
Lines 2 through 2*H+2: | 2*W+1 characters that represent the maze |
SAMPLE INPUT (file maze1.in)
5 3 +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+
OUTPUT FORMAT
A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze.
SAMPLE OUTPUT (file maze1.out)
9
The lower left-hand corner is *nine* steps from the closest exit.
题意:
给出 W(1 ~ 38),H(1 ~ 100),代表有 2 * W + 1 列,2 * H + 1 行的一个地图。根据这个地图,输出任意一点至少要逃出迷宫的步数,如样例输出9,就是最左下角的格子逃出去至少需要9步。
思路:
BFS。要求任意一点都必须逃离迷宫,而且需要最少的步数,那么挑选离出口最远的点BFS即可求出最少步数。因为不知道哪一点最远,故每一格都BFS一次,求出每个点的最小值,同时比较大小取最大值即可。
AC:
/* TASK:maze1 LANG:C++ ID:sum-g1 */ #include <cstdio> #include <iostream> #include <string.h> #include <algorithm> #include <queue> using namespace std; typedef struct { int x,y,step; }node; node no[50000]; char Map[205][100]; bool End[205][100],vis[205][100]; int dir[4][2] = {-2,0,0,-2,2,0,0,2}; int n,m,max_step; bool test(int way,int x,int y) { if(way == 0 && Map[x - 1][y] == ' ') return true; if(way == 1 && Map[x][y - 1] == ' ') return true; if(way == 2 && Map[x + 1][y] == ' ') return true; if(way == 3 && Map[x][y + 1] == ' ') return true; return false; } int bfs(int x,int y) { if(End[x][y]) return 1; node a; memset(vis,0,sizeof(vis)); queue<node> q; while(!q.empty()) q.pop(); a.x = x;a.y = y;a.step = 1; q.push(a); vis[a.x][a.y] = 1; while(!q.empty()) { node now = q.front();q.pop(); for(int i = 0;i < 4;i++) { node b; b.x = now.x + dir[i][0]; b.y = now.y + dir[i][1]; b.step = now.step + 1; if(b.x >= 1 && b.x <= 2 * n - 1 && b.y >= 1 && b.y <= 2 * m - 1 && !vis[b.x][b.y] && test(i,now.x,now.y)) { q.push(b); vis[b.x][b.y] = 1; if(End[b.x][b.y]) return b.step; } } } } void init() { for(int i = 0;i < 2 * n + 1;i++) for(int j = 0;j < 2 * m + 1;j++) End[i][j] = false; for(int i = 1;i <= 2 * n - 1;i += 2) { if(Map[i][0] == ' ') End[i][1] = true; if(Map[i][2 * m] == ' ') End[i][2 * m - 1] = true; } for(int j = 1;j <= 2 * m - 1;j += 2) { if(Map[0][j] == ' ') End[1][j] = true; if(Map[2 * n][j] == ' ') End[2 * n - 1][j] = true; } max_step = -1; } int main() { freopen("maze1.in","r",stdin); freopen("maze1.out","w",stdout); scanf("%d%d",&m,&n); getchar(); for(int i = 0;i < 2 * n + 1;i++) gets(Map[i]); init(); for(int i = 1;i <= 2 * n - 1;i += 2) for(int j = 1;j <= 2 * m - 1;j += 2) max_step = max(max_step,bfs(i,j)); printf("%d\n",max_step); return 0; }
相关推荐
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
降群法解魔方 哈哈师大 使用双向BFS搜素
动态内存+BFS #include #include #include #include using namespace std; void BFS(list<int> *the_a,int the_N,int the_S,int *the_b){ int *m=new int[the_N]; for(int k1=0;k1;k1++) m[k1]=0; m[the_S-1]=1; ...
bfsk系统仿真 bfsk系统仿真 bfsk系统仿真
这是山东大学可视化课程项目,用js实现的BFS和DFS,详细的展示了BFS和DFS的运行过程,网页可交互。
现有的分布式文件系统(如HDFS等)无法满足低延迟、高可用、跨地域扩展等方面的需求,所以我们从百度搜索的业务特点出发,开发了自己的分布式文件系统BFS。 设计目标 高可靠、高可用通过将数据副本进行多机房、多...
simulink BFSK仿真
详细地介绍BFS的思路模式以及用几个案例教授怎么运用BFS去解题。
code for bfs algorithm
BFS广度优先搜索算法视频演示。宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索...
DFS和BFS算法的实现,使用C++语言,适合数据结构初学者学习。
压缩文件里的“bfs-node.h”是头文件,需要在Visual Studio中附加在头文件。这里采取了有向图的邻接链表表现形式,起作用的bfs函数的代码格式参考了《算法导论》这本书上的伪代码。
Matlab仿真BPSK,BFSK,BASK,BDPSK相干解调以及非相干解调的误码率。
采用共轭方向法中的BFS方法进行优化,程序中采用简单算例,并附有文档说明
cuda code of bfs algorithm
bfsk在高斯信道和锐利多径衰落信道中传输的性能比较,使用simulink!!!!!!!!!
二叉树遍历BFS与DFS详细代码python版
以动画的方式采用bfs算法实现八数码问题的解决,html文件可直接运行
this is code for bfs in c++
C++ BFS迷宫.cpp