记录编号	97022	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 花园栅栏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-04-16 13:02:50	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int SIZEN=110;
int N=101;
int X,Y,Z;
bool hf[SIZEN][SIZEN]={0};//某一格的左面有没有栅栏
bool vf[SIZEN][SIZEN]={0};//某一格的下面有没有栅栏
int dx[5]={1,-1,0,0},dy[5]={0,0,-1,1};
//0123东西南北
bool visit[SIZEN][SIZEN]={0};
void BFS(void){
	queue<pair<int,int> > Q;
	int sum=0;
	Q.push(make_pair(0,0));
	visit[0][0]=true;
	sum++;
	while(!Q.empty()){
		int x=Q.front().first,y=Q.front().second;Q.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<0||nx>N||ny<0||ny>N) continue;
			if(visit[nx][ny]) continue;
			if((i==0||i==1)&&hf[max(x,nx)][ny]) continue;
			if((i==2||i==3)&&vf[nx][max(y,ny)]) continue;
			Q.push(make_pair(nx,ny));
			visit[nx][ny]=true;
			sum++;
		}
	}
	printf("%d\n",(N+1)*(N+1)-sum);
}
int dirid(char ch){
	if(ch=='E') return 0;
	if(ch=='W') return 1;
	if(ch=='S') return 2;
	if(ch=='N') return 3;
}
void makemove(void){
	scanf("%d%d%d",&X,&Y,&Z);
	X++,Y++;
	char ch;
	int step;
	for(int i=1;i<=Z;i++){
		cin>>ch>>step;
		for(int k=1;k<=step;k++){
			if(ch=='E') vf[X][Y]=true;
			else if(ch=='W') vf[X-1][Y]=true;
			else if(ch=='S') hf[X][Y-1]=true;
			else if(ch=='N') hf[X][Y]=true;
			X+=dx[dirid(ch)],Y+=dy[dirid(ch)];
		}
	}
}
int main(){
	freopen("fence.in","r",stdin);
	freopen("fence.out","w",stdout);
	makemove();
	BFS();
	return 0;
}