题解 P6226 【[BalticOI 2019 Day1]潜艇】

hsfzLZH1 · 2020-03-21 21:30:19 · 题解

题目大意

给定一个 R\times C 的地图，和一个长度为 M 的操作序列。潜艇的初始位置可能是没有障碍的任意位置，每次操作会按操作对应的方向前进一步，若操作为 ? 则可能是任意方向，目标位置不能有障碍物。求出潜艇最后可能的位置有多少种。

Subtask#1

考虑同时计算一次操作后每个位置上是否可能有潜艇。令 f[t][x][y] 表示在前 t 次操作后 (x,y) 这个位置上是否可能有潜艇。每次根据 f[t-1] 来计算 f[t] 的值，若 t-1 次操作后 (x,y) 位置上可能有潜艇且操作符为 N 且位置 (x-1,y) 上不为障碍物，则令 f[t][x-1][y]=1 ，其他操作符以此类推。若操作符为 ? ，则对四个方向同时进行更新。最后 f[M] 中 1 的个数即为答案。时间复杂度为 O(RCM) ，使用滚动数组压缩掉第一维，则空间复杂度为 O(RC) 。

Subtask#3

考虑对 Subtask#2 的解法进行优化。观察到 f 数组的值均为 0 或 1 ，每个操作符对 f 数组的改变可以视为将 f 数组向一个方向移一格，考虑使用 bitset 进行二进制压缩。将一个数组写成一个二进制串，则对每个操作符的运算都可以用位移运算和与运算来实现，只需注意边界即可。

时间复杂度为 O(\dfrac {RCM} w) ，空间复杂度为 O(\dfrac {RC} w) 。

参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int maxn=510;
int r,c,m,ans;
char mp[maxn][maxn],op[5010];
bitset<maxn*maxn>st,f,W,E;
int main()
{
    scanf("%d%d%d",&r,&c,&m);
    for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
    scanf("%s",op);
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)
    {
        if(mp[i][j]=='.')st[(i-1)*c+j]=1;//st 表示所有非障碍格
        if(j!=1)E[(i-1)*c+j]=1;//E 操作时不能移动最右一列
        if(j!=c)W[(i-1)*c+j]=1;//W 操作时不能移动最左一列
    }
    f=st;
    /*
    for(int i=0;i<m;i++)//这里是 Subtask#2 的实现
    {
        cur^=1;
        for(int j=1;j<=r;j++)for(int k=1;k<=c;k++)f[j][k][cur]=0;
        for(int j=1;j<=r;j++)for(int k=1;k<=c;k++)if(f[j][k][cur^1])
        {
            if(op[i]=='N'||op[i]=='?')if(j-1>=1&&mp[j-1][k]=='.')f[j-1][k][cur]=1;
            if(op[i]=='S'||op[i]=='?')if(j+1<=r&&mp[j+1][k]=='.')f[j+1][k][cur]=1;
            if(op[i]=='E'||op[i]=='?')if(k+1<=c&&mp[j][k+1]=='.')f[j][k+1][cur]=1;
            if(op[i]=='W'||op[i]=='?')if(k-1>=1&&mp[j][k-1]=='.')f[j][k-1][cur]=1;
        }
    }
    */
    for(int i=0;i<m;i++)
    {
        if(op[i]=='N')f=(f>>c)&st;
        if(op[i]=='S')f=(f<<c)&st;
        if(op[i]=='W')f=(f>>1)&st&W;
        if(op[i]=='E')f=(f<<1)&st&E;
        if(op[i]=='?')f=((f>>c)|(f<<c)|((f>>1)&W)|((f<<1)&E))&st;
    }
    printf("%d\n",f.count());
    return 0;
}