BOI Day1 nautilus 题解

题意：

按照给出的字符串的方向走后，最终可能处于多少个位置。

分析:

可以发现，每走一步就是对当前所有可能的位置统一进行一次移动，遇到障碍或超出边界就舍弃这个位置a。

如果我们给这个矩阵的每个位置附上一个编号，那么我们发现：上下左右移动一格等价于编号+1、-1、+C、-C。

所以，我们不难想到将矩阵表示为一个二进制的01串，如果当前可能到达这个位置，那么该处为1，否则为零。

一次移动等价于二进制的左移右移，遇到问号相当于将上下左右移动都做一遍的结果或起来；

遇到障碍或超出边界舍弃这个位置就相当于：这个二进制数对所有合法的位置&1，对所有非法的位置&0。

R*C<=2500,所以我们可以用bitset来实现这个操作，bitset的count()函数会返回二进制中1的个数。

一个实现上的细节：左右移动一格后可能会移到上一行的末尾和下一行的开头位置，为了避免这种情况，我们需要在矩阵边界处补上两列非法位置。

详见代码：

#include<cstdio>
#include<bitset>
using namespace std;
#define MAXN 5010
bitset<251000>a,s;
char t[MAXN];
int n,m,K;
int main()
{
	freopen("nautilus.in","r",stdin);
	freopen("nautilus.out","w",stdout);
	scanf("%d%d%d",&n,&m,&K);
	m+=2;
	for(int i=0;i<n;i++)
	{
		scanf("%s",t+1);
		for(int j=0;j<m;j++)
			if(t[j]=='.') s[i*m+j]=1;
	}
	a=s;
	scanf("%s",t);
	for(int i=0;i<K;i++)
	{
		if(t[i]=='?') a=((a>>1)|(a<<1)|(a>>m)|(a<<m))&s;
		else if(t[i]=='N') a=(a>>m)&s;
		else if(t[i]=='S') a=(a<<m)&s;
		else if(t[i]=='W') a=(a>>1)&s;
		else if(t[i]=='E') a=(a<<1)&s;
	}
	printf("%d\n",(int)a.count());
}