2.4.2 Overfencing 穿越栅栏
时间： 1ms 内存：64M
描述：
农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。
给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X或Y轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步） 这是一个W=5,H=3的迷宫：+-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。
输入：
第一行： W和H（用空格隔开）
第二行至第2*H+2行： 每行2*W+1个字符表示迷宫
输出：
输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
示例输入：
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+示例输出：
9
提示：
参考答案（内存最优[1360]）：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define W 80
#define H 220
typedef struct
{
int x;
int y;
}pos;
int col[4]={-1,0,1,0};
int row[4]={0,1,0,-1};
string graph[H];
int w,h;
bool isvis[H][W];
int xmin[H][W];
int res;
void bfs(pos tmp)
{
int i,j;
pos tmpo,tmpi;
queue<pos> q;
for(i=0;i<H;i++)
for(j=0;j<W;j++)
isvis[i][j]=false;
q.push(tmp);
isvis[tmp.x][tmp.y]=true;
xmin[tmp.x][tmp.y]=1;
while(!q.empty())
{
tmpo=q.front();
q.pop();
for(i=0;i<4;i++)
{
tmpi.x=tmpo.x+col[i]*2;
tmpi.y=tmpo.y+row[i]*2;
if(tmpi.x>=1&&tmpi.x<=h*2-1&&tmpi.y>=1&&tmpi.y<=w*2-1&&graph[tmpo.x+col[i]][tmpo.y+row[i]]==' '&&isvis[tmpi.x][tmpi.y]==false)
{
isvis[tmpi.x][tmpi.y]=true;
if(xmin[tmpi.x][tmpi.y]>xmin[tmpo.x][tmpo.y]+1)
xmin[tmpi.x][tmpi.y]=xmin[tmpo.x][tmpo.y]+1;
q.push(tmpi);
}
}
}
}
int main()
{
int i,j;
pos tmp;
cin>>w>>h;
getline(cin,graph[0]);
for(i=0;i<=h*2;i++)
getline(cin,graph[i]);
for(i=1;i<=h*2-1;i+=2)
for(j=1;j<=w*2-1;j+=2)
xmin[i][j]=21000;
for(i=1;i<=h*2-1;i+=2)
{
for(j=1;j<=w*2-1;j+=2)
{
if((graph[i+1][j]==' '&&i+2==h*2+1)||
(graph[i-1][j]==' '&&i-2==-1)||
(graph[i][j+1]==' '&&j+2==w*2+1)||
(graph[i][j-1]==' '&&j-2==-1))
{
tmp.x=i;
tmp.y=j;
bfs(tmp);
}
}
}
for(i=1;i<=h*2-1;i+=2)
for(j=1;j<=w*2-1;j+=2)
if(res<xmin[i][j])
res=xmin[i][j];
cout<<res<<endl;
return 0;
}
参考答案（时间最优[16]）：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define W 80
#define H 220
typedef struct
{
int x;
int y;
}pos;
int col[4]={-1,0,1,0};
int row[4]={0,1,0,-1};
string graph[H];
int w,h;
bool isvis[H][W];
int xmin[H][W];
int res;
void bfs(pos tmp)
{
int i,j;
pos tmpo,tmpi;
queue<pos> q;
for(i=0;i<H;i++)
for(j=0;j<W;j++)
isvis[i][j]=false;
q.push(tmp);
isvis[tmp.x][tmp.y]=true;
xmin[tmp.x][tmp.y]=1;
while(!q.empty())
{
tmpo=q.front();
q.pop();
for(i=0;i<4;i++)
{
tmpi.x=tmpo.x+col[i]*2;
tmpi.y=tmpo.y+row[i]*2;
if(tmpi.x>=1&&tmpi.x<=h*2-1&&tmpi.y>=1&&tmpi.y<=w*2-1&&graph[tmpo.x+col[i]][tmpo.y+row[i]]==' '&&isvis[tmpi.x][tmpi.y]==false)
{
isvis[tmpi.x][tmpi.y]=true;
if(xmin[tmpi.x][tmpi.y]>xmin[tmpo.x][tmpo.y]+1)
xmin[tmpi.x][tmpi.y]=xmin[tmpo.x][tmpo.y]+1;
q.push(tmpi);
}
}
}
}
int main()
{
int i,j;
pos tmp;
cin>>w>>h;
getline(cin,graph[0]);
for(i=0;i<=h*2;i++)
getline(cin,graph[i]);
for(i=1;i<=h*2-1;i+=2)
for(j=1;j<=w*2-1;j+=2)
xmin[i][j]=21000;
for(i=1;i<=h*2-1;i+=2)
{
for(j=1;j<=w*2-1;j+=2)
{
if((graph[i+1][j]==' '&&i+2==h*2+1)||
(graph[i-1][j]==' '&&i-2==-1)||
(graph[i][j+1]==' '&&j+2==w*2+1)||
(graph[i][j-1]==' '&&j-2==-1))
{
tmp.x=i;
tmp.y=j;
bfs(tmp);
}
}
}
for(i=1;i<=h*2-1;i+=2)
for(j=1;j<=w*2-1;j+=2)
if(res<xmin[i][j])
res=xmin[i][j];
cout<<res<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。