Problem 2250 不可能弹幕结界
Accept:30 Submit: 76
Time Limit: 1000 mSec Memory Limit : 65536 KB
ProblemDescription
咲夜需要穿过一片弹幕区，由于咲夜发动了符卡“TheWorld”,所以弹幕是静止的。这片弹幕区以一个n*m的矩阵的形式给出。
‘.’表示这个位置是安全的，’x’表示这个位置上是有子弹的，禁止通行。咲夜每次能向左、右、下三个方向的相邻格子走，但是不能向上走。 同时由于时间有限，咲夜在进入每一行之后最多只能横向走k步。你可以简单地认为我们的目标就是从第0行走到第n+1行，起点和终点可以是在第0行和第n+1行的任意位置，当然第0行和第n+1行都是没有弹幕的。
然而这是号称不可能的弹幕结界，所以咲夜很可能无法穿过这片弹幕，所以咲夜准备了一个只能使用一次的技能，纵向穿越，她可以从任意位置直接穿越到另外任意一行的同一个位置(所在列不变)，当然她只能向下穿越，不能向上穿越。穿越的距离越远，耗费的资源自然越多，所以她想知道最短的穿越距离，才能使她成功通过这片弹幕区。
Input
输入包含多组数据。
对于每组数据：
第一行输入三个整数n,m,k,如上所述。
接下下输入一个n×m的矩阵，’.’表示当前这格没有子弹，是安全的，’x’表示这各有子弹，禁止通行。
N<=1000,k<=m<=1000
Output
对于每组数据输出一个整数，表示最短的穿越距离。
SampleInput
6 5 2
x.x..
..xx.
.xxx.
xx.xx
xx..x
..x.x
4 4 1
.xxx
.xxx
...x
xx.x
Sample Output
3
2
Hint
对于第一组样例，最优解是从第一行第二列走到第三行第一列，然后跳到第6行第一列，穿越距离为(6 – 3) = 3。
【思路】由于限制条件有横向步数，所以我们要维护从起点到某一个点的最小横向步数，用vis[i][j]=x来表示从起点能否走到这个点，如果能走到，则走到这个点时的最小横向步数为x,否则为INF。
因为只能穿越一次，所以穿越前后的两个点必须分别与起点和终点可达，所以我们考虑分别从起点和终点开始进行两次BFS，得到vis1数组和vis2数组。然后根据穿越是在同一列的性质，对每一列算出它从起点最下能到达的位置和从终点最上能到达的位置。设为Maxdown，Maxup(初始值为-1)。
下面考虑几种情况：
1. 起点直接能到终点，显然为0.
4 4 2
.xxx
.xxx
...x
xx.x
2. 只考虑向下的
如上图，显然最小为2(Maxdown=2,4-2=2)
3. 只考虑向上的如上图，显然最小为3(Maxup=2,2+1=3)
可能有疑问，为什么要这样取处理这两种情况呢，又不一定是最优的，其实主要是为了把有-1的情况删去方便后面的讨论。
4. Maxdown==Maxup (千万不要认为是0！！！)4 4 1 (即题目第二个样例)
.xxx
.xxx
...x
xx.x
显然往下走到(2,2)已经不能往右走了，往上走到(2,2)也已经不能往左走了,这样的话结果就包含在上面的2和3里了，直接continue.
5. 剩下的情况
6 5 2
x.x..
..xx.
.xxx.
x..xx
xx..x
.x.xx
如图，第二列Maxdown=1,Maxup=3,故结果为Maxup-Maxdown,这时候就不用考虑会发生4这种情况了，因为是直接穿越的。
可能写得很不清楚，但多画画几种情况应该会慢慢理解的。。。
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
typedef long long ll;
const int maxn=1005;
const int mod = 20090717;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n,m,k;
int vis1[maxn][maxn];
int vis2[maxn][maxn];
char mp[maxn][maxn];
const int dir1[3][2]={{1,0},{0,1},{0,-1}};
const int dir2[3][2]={{-1,0},{0,1},{0,-1}};
struct node
{
int x,y,step;
}now,nex;
bool inbound(node a)
{
return a.x>=0&&a.x<n&&a.y>=0&&a.y<m;
}
void BFS1()
{
mst(vis1,0x3f);
queue<node>q;
for(int i=0;i<m;i++)
{
if(mp[0][i]=='.')
{
now.x=0;
now.y=i;
now.step=0;
q.push(now);
vis1[0][i]=0;
}
}
while(q.size())
{
now=q.front();
q.pop();
for(int i=0;i<3;i++)
{
nex.x=now.x+dir1[i][0];
nex.y=now.y+dir1[i][1];
if(i==0) nex.step=0;
else nex.step=now.step+1;
if(inbound(nex)&&nex.step<=k&&mp[nex.x][nex.y]!='x')
{
if(vis1[nex.x][nex.y]>nex.step)
{
vis1[nex.x][nex.y]=nex.step;
q.push(nex);
}
}
}
}
}
void BFS2()
{
mst(vis2,0x3f);
queue<node>q;
for(int i=0;i<m;i++)
{
if(mp[n-1][i]=='.')
{
now.x=n-1;
now.y=i;
now.step=0;
q.push(now);
vis2[n-1][i]=0;
}
}
while(q.size())
{
now=q.front();
q.pop();
for(int i=0;i<3;i++)
{
nex.x=now.x+dir2[i][0];
nex.y=now.y+dir2[i][1];
if(i==0) nex.step=0;
else nex.step=now.step+1;
if(inbound(nex)&&nex.step<=k&&mp[nex.x][nex.y]!='x')
{
if(vis2[nex.x][nex.y]>nex.step)
{
vis2[nex.x][nex.y]=nex.step;
q.push(nex);
}
}
}
}
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&k))
{
for(int i=0;i<n;i++)
{
scanf("%s",mp[i]);
}
BFS1();
BFS2();
int flag=0;
for(int i=0;i<m;i++)
{
if(vis1[n-1][i]!=INF)
{
flag=1;
break;
}
}
if(flag)
{
puts("0");
continue;
}
int ans=n+1;
for(int i=0;i<m;i++)
{
int Maxdown=-1;
int Maxup=-1;
for(int j=0;j<n;j++)
{
if(vis1[j][i]!=INF) Maxdown=j;
if(vis2[j][i]!=INF&&Maxup==-1) Maxup=j;
}
if(Maxdown!=-1) ans=min(ans,n-Maxdown);
if(Maxup!=-1) ans=min(ans,Maxup+1);
if(Maxdown==-1||Maxup==-1) continue;
if(Maxdown==Maxup)
{
continue;
}
else ans=min(ans,Maxup-Maxdown);
}
printf("%d\n",ans);
}
return 0;
}