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