记录编号	6676	评测结果	AAAAAAAAAA
题目名称	[USACO Dec08] 花园栅栏	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2008-11-03 22:43:23	内存使用	1.21 MiB

#include <iostream>

using namespace std;

const int MAX=500;

struct point
{
	int x,y;
};

template <typename T> class tQueue
{
	private:
	class tqlist
	{
	public:
		tqlist *next;
		T value;
		tqlist(T tv):value(tv)
		{
			next=0;
		}
	};
	tqlist *first,*last;
	public:
	int size;
	void ins(T value)
	{
		if (first)
			last=last->next=new tqlist(value);
		else
			first=last=new tqlist(value);
		size++;
	}
	T pop()
	{
		size--;
		T rtn=first->value;
		tqlist *tp=first;
		first=first->next;
		delete tp;
		return rtn;
	}
	tQueue()
	{
		first=last=0;
		size=0;
	}
};

point cur;
int Map[MAX][MAX];
tQueue<point> Q;
int dx[]={0,0,2,-2},dy[]={2,-2,0,0};
int ddx[]={0,0,1,-1},ddy[]={1,-1,0,0};
int Alls,S,Ans;

void go(char c,int P)
{
	int i;
	P*=2;
	if (c=='N')
	{
		for (i=1;i<=P;i++,cur.y++)
		{
			Map[cur.x][cur.y]=-1;
		}
	}
	else if (c=='S')
	{
		for (i=1;i<=P;i++,cur.y--)
		{
			Map[cur.x][cur.y]=-1;
		}
	}
	else if (c=='E')
	{
		for (i=1;i<=P;i++,cur.x++)
		{
			Map[cur.x][cur.y]=-1;
		}
	}
	else if (c=='W')
	{
		for (i=1;i<=P;i++,cur.x--)
		{
			Map[cur.x][cur.y]=-1;
		}
	}
}

void init()
{
	int i,N,p;
	char c;
	freopen("fence.in","r",stdin);
	freopen("fence.out","w",stdout);
	scanf("%d%d%d\n",&cur.x,&cur.y,&N);
	cur.x*=2;
	cur.y*=2;
	cur.x+=10;
	cur.y+=10;
	Map[cur.x][cur.y]=-1;
	for (i=1;i<=N;i++)
	{
		scanf("%c%d\n",&c,&p);
		go(c,p);
	}
	Alls=110*110;
}

inline bool inrange(point p)
{
	return p.x>=1 && p.x<=220 && p.y>=1 && p.y <=220;
}

void debug()
{
	int i,j;
	for (i=1;i<=220;i+=2)
	{
		for (j=1;j<=220;j+=2)
		{
			cout << Map[i][j];
		}
		cout << endl;
	}
}

void floodfill(point i)
{
	point j,p;
	int k;
	Q.ins(i);
	Map[i.x][i.y]=1;
	while (Q.size)
	{
		i=Q.pop();
		S++;
		for (k=0;k<4;k++)
		{
			j.x=i.x+dx[k];
			j.y=i.y+dy[k];
			p.x=i.x+ddx[k];
			p.y=i.y+ddy[k];
			if (inrange(j))
			{
				if (Map[p.x][p.y]!=-1)
				{
					if (Map[j.x][j.y]==0)
					{
						Q.ins(j);
						Map[j.x][j.y]=1;
					}
				}
			}
		}
	}
}

void solve()
{
	point i;
	for (i.x=1;i.x<=220;i.x+=2)
	{
		i.y=1;
		if (Map[i.x][i.y]==0)
			floodfill(i);
		i.y=219;
		if (Map[i.x][i.y]==0)
			floodfill(i);
	}
	for (i.y=1;i.y<=220;i.y+=2)
	{
		i.x=1;
		if (Map[i.x][i.y]==0)
			floodfill(i);
		i.x=219;
		if (Map[i.x][i.y]==0)
			floodfill(i);
	}
	//debug();
	Ans=Alls-S;
}

int main()
{
	init();
	solve();
	cout << Ans << endl;
	return 0;
}