题解 P6226 [BalticOI 2019 Day1] 潜艇

· · 题解

题解 P6226 [BalticOI 2019 Day1] 潜艇

题意

很清楚，忽略。

分析

看到这种字符串题很容易想到直接广度优先搜索，复杂度 O(rc4^m)。

很显然承受不了，所以考虑 DP。

状态设计

设 f_{i,x,y} 表示执行完前 i 个操作后位置 (x,y) 能否作为终点。

设命令字符串为 s，原地图为 a。

状态转移

f_{i,x,y}=f_{0,x,y} \operatorname{and} \begin{cases} f_{i-1,x+1,y} & s_i=\texttt{N}\\ f_{i-1,x-1,y} & s_i=\texttt{S}\\ f_{i-1,x,y+1} & s_i=\texttt{W}\\ f_{i-1,x,y-1} & s_i=\texttt{E}\\ f_{i-1,x+1,y} \operatorname{or} f_{i-1,x-1,y} \operatorname{or} f_{i-1,x,y-1} \operatorname{or} f_{i-1,x,y+1} & s_i=\texttt{?}\\ 0 & \text{otherwise} \end{cases}

初始状态

f_{0,x,y}= \begin{cases} 1 & a_{x,y}=\texttt{.}\\ 0 & a_{x,y}=\texttt{\#}\\ 0 & \text{otherwise} \end{cases}

经过观察可以发现状态转移只需要两维，所以可以直接滚动省略掉第一维。

时间复杂度 O(rcm)，仍然难以通过此题。

发现 f 数组的值仅为 0 或 1，所以我们可以直接使用 std::bitset 进行压位砍掉常数。

代码

//the code is from chenjh
#include<cstdio>
#include<bitset>
int r,c,m;
std::bitset<505> a[505],f[505],g[505];//a 为初始状态，f 为过程状态，g 为辅助状态。
int main(){
    scanf("%d%d%d",&r,&c,&m);
    for(int i=1;i<=r;i++){
        scanf(" ");
        for(int j=1;j<=c;j++) a[i][j]=getchar()=='.';
        f[i]=a[i];
    }
    scanf(" ");
    for(char c;m--;){
        c=getchar();
        if(c=='N'){
            for(int i=1;i<r;i++)f[i]=f[i+1]&a[i];
            f[r].reset();
        }
        else if(c=='S'){
            for(int i=r;i>1;--i)f[i]=f[i-1]&a[i];
            f[1].reset();
        }
        else if(c=='W'){
            for(int i=1;i<=r;i++)f[i]=(f[i]>>1)&a[i];
        }
        else if(c=='E'){
            for(int i=1;i<=r;i++)f[i]=(f[i]<<1)&a[i];
        }
        else if(c=='?'){
            for(int i=1;i<=r;i++)g[i]=(f[i-1]|f[i+1]|(f[i]<<1)|(f[i]>>1))&a[i];
            for(int i=1;i<=r;i++)f[i]=g[i];
        }
        else break;//直接转移即可。
    }
    int s=0;
    for(int i=1;i<=r;i++)s+=f[i].count();//统计有多少个值为 1，即有多少个可行的点。
    printf("%d\n",s);
    return 0;
}