首页 > 代码库 > 【bfs】noip模拟赛 栅栏迷宫
【bfs】noip模拟赛 栅栏迷宫
1、栅栏迷宫
题目描述
田野上搭建了一个黄金大神专用的栅栏围成的迷宫。幸运的是，在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点，走出迷宫的最少步数）。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，黄金大神让你必须只会水平或垂直地在X或Y轴上移动，你不能从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）这是一个W=5,H=3的迷宫：
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。
INPUT FORMAT:
(file maze.in)
第一行： W和H（用空格隔开）
第二行至第2*H+1行： 每行2*W+1个字符表示迷宫
OUTPUT FORMAT:
(file maze.out)
输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
SAMPLE INPUT
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
SAMPLE OUTPUT
9
善良的学长:样例输入可以复制进记事本或者文本文档这样看起来更加直观！！！=v=
思路
这题其实很可怕!!
最讨厌的就是去找入口出口。。我虽然过了那是数据太水……你看题目描述可不可以迷宫就建一半剩一半放那儿，那暴力找出入口就根本不行。
解决方法应该是在外面开一个出入口，然后搜索进入整个图，如果不是找到真正的出入口就会多走没必要的路，这样程序会自动剔除这种情况
搜索的时候注意一下向四面搜索每次走两步即可
代码
#include <iostream>#include <iomanip>#include <fstream>#include <cmath>#include <cstring>using namespace std;struct note{ int x,y;}queue[200000];int p1[4][2]={{-2,0},{0,2},{2,0},{0,-2}};int p2[4][2]={{-1,0},{0,1},{1,0},{0,-1}};int a[500][500];int value[500][500];int head,tail,w,h;ifstream fin("maze.in");ofstream fout("maze.out");void input(){ fin>>w>>h; w=w*2+1;h=h*2+1; for (int i=1;i<=h;i++) { fin.get(); for (int j=1;j<=w;j++) { a[i][j]=fin.get(); if ( (i==1)&&(a[i][j]==‘ ‘) ) {tail++; queue[tail].x=i+1;queue[tail].y=j; value[i+1][j]=1;} if ( (i==h)&&(a[i][j]==‘ ‘) ) {tail++; queue[tail].x=i-1;queue[tail].y=j; value[i-1][j]=1;} if ( (j==1)&&(a[i][j]==‘ ‘) ) {tail++; queue[tail].x=i;queue[tail].y=j+1; value[i][j+1]=1;} if ( (j==w)&&(a[i][j]==‘ ‘) ) {tail++; queue[tail].x=i;queue[tail].y=j-1; value[i][j-1]=1;} } }}void bfs(){ head=0; int wx,wy,tx,ty,nx,ny; //wx,wy是p2的，tx,ty是p1的，nx,ny是现在的 while (head<=tail) { head++; for (int i=0;i<=3;i++) { tx=queue[head].x+p1[i][0];ty=queue[head].y+p1[i][1]; wx=queue[head].x+p2[i][0];wy=queue[head].y+p2[i][1]; if ( (tx>0)&&(tx<h)&&(ty>0)&&(ty<w)&&(a[wx][wy]==‘ ‘)&&(value[tx][ty]==0) ) { tail++; queue[tail].x=tx; queue[tail].y=ty; value[tx][ty]=value[queue[head].x][queue[head].y]+1; } } }}void output(){ int best=0; for (int i=1;i<=h;i++) for (int j=1;j<=w;j++) if (value[i][j]>best) best=value[i][j]; fout<<best<<endl;}int main(){ input(); bfs(); output(); return 0;}
结果
【bfs】noip模拟赛 栅栏迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。