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

Код:
#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;
}