http://acm.pku.edu.cn/JudgeOnline/problem?id=1132

http://acm.pku.edu.cn/JudgeOnline/images/1132/1132_1.gif

Код:
#include <assert.h>
#include <iostream>
using namespace std;

const int cMaxExtent= 32;
const unsigned int FALSE=0;

// Coordinate system:
//          N
//   Y      ^
//   ^  W <-+-> E
//   |      v
//   |      S
//   |
//  -+------> X
// O |

// A horizontal path element stored at (x, y) goes from (x, y) to (x+1, y)
// A vertical path element stored at (x, y) goes from (x, y) to (x, y+1)

class Path {
public:
	Path ()
{ Clear (); }
	void Clear ();

	void Go (char direction);
	
	void SetPos (int x, int y);
	
	bool HEdge(int x, int y) const
{ return hEdges [x][y]; }
	bool VEdge(int x, int y) const
{ return vEdges [x][y]; }
	
	void CheckClosed () const;
	
protected:
	bool hEdges [cMaxExtent][cMaxExtent];
	bool vEdges [cMaxExtent][cMaxExtent];
	int  xPos, yPos;

// path integrity checks
	int  startXPos, startYPos;
	int	 lefts, rights, ups, downs;
};


// A bit in the bit map extends from (x, y) to (x+1, y+1)

class Bitmap {
public:
	Bitmap ()
{ Clear (); }
	void Clear ();
	
	bool GetBit (int x, int y)
{ return bitmap [x][y]; }
	void SetBit (int x, int y, bool value= true)
{ bitmap [x][y]= value; }

protected:
	bool bitmap [cMaxExtent][cMaxExtent];
};


void FindOutline (const Path& path, Bitmap& bitmap);


void Path::Clear ()
{
//	int x, y;
	for (int x= 0; x < cMaxExtent; x++)
for (int y= 0; y < cMaxExtent;y++) {
	hEdges [x][y] = false;
	vEdges [x][y] = false;
}
	xPos= yPos= 1;
	startXPos= startYPos= -1;
	lefts= rights= ups= downs= 0;
}


void Path::SetPos (int x, int y)
{
	xPos= startXPos= x;
	yPos= startYPos= y;
	assert (xPos > 0 && xPos < cMaxExtent);
	assert (yPos > 0 && yPos < cMaxExtent);
}


void Path::Go (char direction)
{
	switch (direction) {
	case 'W':
xPos--;
hEdges [xPos][yPos] = true;
lefts++;
break;
	case 'E':
hEdges [xPos][yPos] = true;
xPos++;
rights++;
break;
	case 'N':
vEdges [xPos][yPos] = true;
yPos++;
ups++;
break;
	case 'S':
yPos--;
vEdges [xPos][yPos] = true;
downs++;
break;
	default:
assert (FALSE);
	}
//{static int i=0; printf("%d %d,%d\n",++i,xPos,yPos); }
	assert (xPos > 0 && xPos < cMaxExtent);
	assert (yPos > 0 && yPos < cMaxExtent);
}


void Path::CheckClosed () const
{
	assert (lefts == rights);
	assert (ups == downs);
	assert (xPos == startXPos);
	assert (yPos == startYPos);
}


void Bitmap::Clear ()
{
	int x, y;
	for (x= 0; x < cMaxExtent; x++)
for (y= 0; y < cMaxExtent; y++)
	bitmap [x][y] = false;
}


void FindOutline (const Path& path, Bitmap& bitmap)
{
	bitmap.Clear ();
	
	int x, y;
	
	// Scan path horizontally for vertical path elements
	for (y= 1; y < cMaxExtent; y++) {
x= 1;
while (1) {
	while ( x < cMaxExtent && ! path.VEdge(x, y) )
x++;
	if (x >= cMaxExtent)
break;
	bitmap.SetBit(x-1, y);	// set bit left to path element
	x++;
	
	while (x < cMaxExtent && ! path.VEdge(x, y) )
x++;
	if (x >= cMaxExtent)
assert(FALSE);	// is path not closed?
	bitmap.SetBit(x, y);	// set bit right to path element
	x++;
}
	}

	// Scan path vertically for horizontal path elements
	for (x= 1; x < cMaxExtent; x++) {
y= 1;
while (1) {
	while ( y < cMaxExtent && ! path.HEdge(x, y) )
y++;
	if (y >= cMaxExtent)
break;
	bitmap.SetBit(x, y-1);	// set bit above path element
	y++;
	
	while (y < cMaxExtent && ! path.HEdge(x, y) )
y++;
	if (y >= cMaxExtent)
assert(FALSE);	// is path not closed?
	bitmap.SetBit(x, y);	// set bit below to path element
	y++;
}
	}
}


int main (int, char*[])
{
	Path	path;
	Bitmap	bitmap;
	intnProblems;
	intx, y;
	char	dir;
	int currProblem;
	
	//ifstream is ("border.in");
//	ofstream os ("border.out");
	
	for (currProblem = 1, cin >> nProblems; nProblems > 0; 
	     nProblems--, currProblem++) {
	
path.Clear ();
cin >> x >> y;
path.SetPos (x, y);

cin >> dir;
while (dir >= 'A' && dir <= 'Z') {
	path.Go (dir);
	cin >> dir;
}

path.CheckClosed ();

FindOutline (path, bitmap);

cout << "Bitmap #" << currProblem << endl;
for (y= cMaxExtent-1; y >= 0; y--) {
	for (x= 0; x < cMaxExtent; x++)
if ( bitmap.GetBit (x, y) )
	cout << 'X';
else
	cout << '.';
	cout << endl;
}
cout << endl;
	
	}

	return 0;
}