Problem 2250 不可能弹幕结界
Time Limit: 1000 mSec Memory Limit : 65536 KB
Problem Description
咲夜需要穿过一片弹幕区，由于咲夜发动了符卡“The World”,所以弹幕是静止的。这片弹幕区以一个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
对于每组数据输出一个整数，表示最短的穿越距离。
Sample Input
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。
分析：考虑从上往下走；
状态转移为如果当前点能够到达，那么下一行这一列如果是‘.’的话，那么这个点左右可到达的范围也能到达；
即if(ok(i,j))ok(i+1,l[i+1][j]~r[i+1][j])；这个标记差分即可；
所以预处理每个点左右能到达的范围；
从下往上也一样，最后找一下行间隔最小即可，注意边界；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <bitset> #include <map> #include <queue> #include <stack> #include <vector> #include <cassert> #define rep(i,m,n) for(i=m;i<=n;i++) #define mod 1000000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define sys system("pause") const int maxn=1e3+10; const int N=2e5+10; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;} int n,m,k,t,l[maxn][maxn],r[maxn][maxn],dp[maxn],up[maxn][maxn],dw[maxn][maxn]; char a[maxn][maxn]; int main() { int i,j; while(~scanf("%d%d%d",&n,&m,&k)) { rep(i,1,n)scanf("%s",a[i]+1); memset(dp,-1,sizeof(dp)); memset(up,0,sizeof(up)); memset(dw,0,sizeof(dw)); rep(i,1,n) { rep(j,1,m) { if(j==1)l[i][j]=j; else l[i][j]=a[i][j-1]!='x'?l[i][j-1]:j; if(l[i][j]<j-k)l[i][j]=j-k; } for(j=m;j>=1;j--) { if(j==m)r[i][j]=j; else r[i][j]=a[i][j+1]!='x'?r[i][j+1]:j; if(r[i][j]>j+k)r[i][j]=j+k; } } rep(i,1,m)if(a[1][i]=='.')up[1][i]=1; rep(i,1,n) { if(i!=1) { rep(j,1,m)up[i][j]+=up[i][j-1]; } rep(j,1,m) { if(up[i][j]&&a[i+1][j]=='.')up[i+1][l[i+1][j]]++,up[i+1][r[i+1][j]+1]--; } } rep(i,1,m)if(a[n][i]=='.')dw[n][i]=1; for(i=n;i>=1;i--) { if(i!=n) { rep(j,1,m)dw[i][j]+=dw[i][j-1]; } rep(j,1,m) { if(dw[i][j]&&a[i-1][j]=='.')dw[i-1][l[i-1][j]]++,dw[i-1][r[i-1][j]+1]--; } } int ret=n+1; for(i=n;i>=1;i--) { rep(j,1,m) { if(up[i][j])ret=min(ret,n+1-i); if(up[i][j]&&dp[j]!=-1)ret=min(ret,dp[j]-i); if(dw[i][j])dp[j]=i,ret=min(ret,i); } } rep(i,1,m)if(up[n][i])ret=0; printf("%d ",ret); } return 0; }