自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:18:46，当前版本为作者最后更新于2020-03-21 21:30:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

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

Subtask#1

$1\le R,C,M\le 100$ ，操作序列中没有 ? 。

此时每一个操作都是确定的。枚举初始位置，按操作模拟潜艇的移动，统计最终潜艇的位置即可。时间复杂度为 $O(RCM)$ ，空间复杂度为 $O(RC)$ 。

Subtask#2

$1\le R,C,M\le 100$

考虑同时计算一次操作后每个位置上是否可能有潜艇。令 $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

$1\le R,C\le 500,1\le M\le 5000$

考虑对 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;
}