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());
}