P1519
HighPerformanceRobot
2019-04-27 21:36:23
#### 吐槽
调了三小时的题目。。~~好吧我都不知道我是第几次调这么长时间了QAQ~~
### 题目大意
给你一个字符串地图，让你求从任意一个出口到迷宫内距出口最长的那个点的距离。
#### 解题思路
每个点都搜暴搜一次最短距离肯定会炸的。那怎么办呢？
我们可以运用反向思维，将两个出口找出来，然后跑两次BFS，更新出口到迷宫内每个点的最短距离，最后最大的就是答案。
还不理解？
那我用常识来帮助你理解一下：
假设从你家到你的学校有1km那么远，那么从你家到你的学校的距离是不是跟从你的学校到你家的距离是一样的，都是1km那么远呢？
同理，迷宫内距出口最远的那个点到出口的距离也就是出口到迷宫内距出口最远的那个点的距离。
但是！
### 坑点来了！
这是个字符串，怎么办？
其实各种办法都可以通用。你直接用字符串当地图也可以，转化成int数组也可以，关键是读入！
读入一个字符串的方法有：
gets，fgets，getline，cin.getline等等。
这里不推荐用gets，原因请自行百度。
但是，注意一个点：如果你读入长和宽的时候用的是cin而不是scanf，那么你就要在读入真正的地图之前多读入一行！
这里又要牵扯到cin跟scanf的区别了：scanf读入完数据后会清掉输入的数据后面的所有空格、Tab和回车，而cin不会。这就造成，你在使用cin的时候，你在长和宽这两个整数后面，还有一个“隐形”的换行符，导致你读入的地图第一行只有一个回车，你说坑不坑？
直接上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int dx[]= {1,-1,0,0},dy[]= {0,0,1,-1};
char x[500]; //读入的字符串，单行读入
int w,h; //宽和长
int ans,now_long;
int fx[2],fy[2];
int f[210][210]; //记录点到任意一个出口的最短距离
int flag[210][210]; //标记是不是墙
bool arr[210][210]; //标记访问过没有
struct node
{
int x,y;
} now;
queue <node> que; //BFS队列
void init()
{
cin.getline(x,500); //我用的cin，所以要多加这一行
for(int i=0; i<210; i++) //初始化
fill(f[i],f[i]+210,INT_MAX),fill(flag[i],flag[i]+210,1);
for(int i=1; i<=h; i++) //读入和转换
{
cin.getline(x,500);
for(int j=1; j<=w; j++)
if(x[j-1]==' ') //是路而不是墙
{
flag[i][j]=0;//标记为可以访问
if((i==1||j==1||i==h||j==w)&&flag[i][j]==0)
fx[now_long]=i,fy[now_long]=j,f[i][j]=1,now_long++; //找出口
}
}
}
void bfs(int x,int y)
{
node begin;
begin.x=x,begin.y=y;
que.push(begin);
arr[x][y]=1;
while(!que.empty())
{
node stor=que.front();
que.pop();
for(int i=0; i<4; i++)
{
int sx=stor.x+dx[i],sy=stor.y+dy[i];
if(sx>0&&sx<=h&&sy>0&&sy<=w&&flag[sx][sy]==0&&arr[sx][sy]==0)
{
arr[sx][sy]=1;
f[sx][sy]=min(f[sx][sy],f[stor.x][stor.y]+1);
now.x=sx,now.y=sy;
que.push(now);
}
}
}
}
int main()
{
// freopen("maze1.in","r",stdin);
// freopen("maze1.out","w",stdout);
ios::sync_with_stdio(0);
cin>>w>>h;
w=2*w+1,h=2*h+1;
init(); //读入+初始化，这样弄个函数主要是方便调试
for(int i=0; i<now_long; i++)
{
bfs(fx[i],fy[i]);
for(int j=0; j<210; j++)
fill(arr[j],arr[j]+210,0); //注意：这里要重新初始化！否则就会WA！
}
for(int i=1; i<=h; i++)
for(int j=1; j<=w; j++)
if(f[i][j]<INT_MAX) //被更新过，因为初值是INT_MAX
ans=max(ans,f[i][j]);
cout<<ans/2<<endl; //这个就自己去想为什么吧，凭各位大佬聪明的脑袋瓜应该不难
return 0;
}
```