题解 P3468 【[POI2008]ROB-Robinson】

· · 题解

求出对于船的左上角，在哪些点是合法的，那么bfs即可。(注意左上角有可能超出地图，即坐标有可能为负)

但要求船全部合法比较麻烦，可以只考虑各个边界的合法。

比如从上往下走时，就只用考虑移动后下边界的合法，因为其他的点都是和原来的船体重叠的。

考虑在(x,y)处下边界合法就是s[x+d_{i}][y+i]=0(i=0..k)，其中d_{i}表示船体从左往右第i列下边界的行，k表示船宽。

那么枚举列，将其他列分别移动d_{i}位再or起来，就得到了这一列的答案。

用bitset实现，时间O(n^3/32)

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
typedef unsigned int ui;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=2000+5;
int n,u;
template <int N>
struct BITSET
{
static const int U=N/32+2;
ui a[U];
void set1(int x)
{
    a[x/32]|=1<<(x&31);
}
bool operator [](int x)
{
    return a[x/32]&(1<<(x&31));
}
};
void or_left_move(ui *a,ui *b,int x)//a|=b<<x  b[0..u]
{
    int dk=x/32,dl=x&31;
    if(!dl)
    {
        rep(i,0,u)a[i+dk]|=b[i];
        return ;
    }
    rep(i,0,u)
    {
        a[i+dk]|=b[i]<<dl;
        a[i+dk+1]|=b[i]>>32-dl; 
    }
}
struct F
{
char s[N][N];
BITSET<N>a[N];
BITSET<N*2>cant[N*2];
int x0,y0;//left up
int x1,y1;//right down
int d[N];
void init()
{
    x0=y0=n;
    rep(i,1,n)
    rep(j,1,n)
    if(s[i][j]=='X')
     a[j].set1(i);
    else
    if(s[i][j]=='r')
    {
        chmin(x0,i);chmin(y0,j);
        chmax(x1,i);chmax(y1,j);
        chmax(d[j],i);
    }
    rep(j,-n,n)
    rep(j2,max(1,j),min(n,j+y1-y0))
    if(d[y0+j2-j]) or_left_move(cant[N+j].a,a[j2].a,N-(d[y0+j2-j]-x0)); 
}
bool judge(int x,int y)
{
    return !cant[N+y][x+1+N];
}
};
F f[4];//f[0] judge if can move down;f[1] up;f[2] right;f[3] left;
int g[N*2][N*2];
struct point
{
    short x,y;
};
point q[N*N*2*2];int tail;
int dis;
void out()
{
    cout<<dis;exit(0);
}
void push(short x,short y)
{
    q[++tail]=(point){x,y};g[N+x][N+y]=dis;
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    cin>>n;u=n/32;
    rep(i,1,n)scanf("%s",f[0].s[i]+1);
    rep(i,1,n)
    rep(j,1,n)f[1].s[n-i+1][n-j+1]=f[2].s[j][n-i+1]=f[3].s[n-j+1][i]=f[0].s[i][j];
    rep(i,0,3)f[i].init(); 
    memset(g,-1,sizeof(g));
    push(f[0].x0,f[0].y0);
    rep(head,1,tail)
    {
        short x=q[head].x,y=q[head].y;
        dis=g[N+x][N+y]+1;
        if(g[N+x+1][N+y]==-1&&f[0].judge(x,y))
        {
            if(x==n) out();
            push(x+1,y);
        }
        int _x=x+f[0].x1-f[0].x0,_y=y+f[0].y1-f[0].y0;
        //(_x,_y)
        if(g[N+x-1][N+y]==-1&&f[1].judge(n-_x+1,n-_y+1))
        {
            if(_x==1) out();
            push(x-1,y); 
        }
        //(_x,y)
        if(g[N+x][N+y+1]==-1&&f[2].judge(y,n-_x+1))
        {
            if(y==n) out();
            push(x,y+1);
        }
        //(x,_y)
        if(g[N+x][N+y-1]==-1&&f[3].judge(n-_y+1,x))
        {
            if(_y==1) out();
            push(x,y-1);
        }
    }
    puts("NIE");
}