/** * Sample solution for Spy Cam * Steven J Zeil, 10/6/2010 */ #include #include #include #include #include #include #include #include using namespace std; struct Rectangle { int xll, yll, xur, yur; Rectangle (int x1=0, int y1=0, int x2=0, int y2=0); bool overlaps (const Rectangle& r) const; bool contains (const Rectangle& r) const; int width() const {return xur - xll;} int height() const {return yur - yll;} Rectangle unionWith (const Rectangle& r) const; Rectangle intersectionWith (const Rectangle& r) const; //pre: overlaps(r) // Generate the Rectangle formed by extending one // edge of this one by one step in the indicated direction // (plus or minus dx, or plus or minus dy) //pre: dx == 0 || dy == 0; !(dx==0 && dy ==0) Rectangle extension (int dx, int dy) const; }; Rectangle::Rectangle (int x1, int y1, int x2, int y2) { xll = min(x1, x2); xur = max(x1, x2); yll = min(y1, y2); yur = max(y1, y2); } bool Rectangle::overlaps (const Rectangle& r) const { if (xll > r.xur) return false; if (xur < r.xll) return false; if (yll > r.yur) return false; if (yur < r.yll) return false; return true; } bool Rectangle::contains (const Rectangle& r) const { return (xll <= r.xll) && (xur >= r.xur) && (yll <= r.yll) && (yur >= r.yur); } Rectangle Rectangle::unionWith (const Rectangle& r) const { Rectangle u (min(xll, r.xll), min(yll, r.yll), max(xur, r.xur), max(yur, r.yur)); return u; } Rectangle Rectangle::intersectionWith (const Rectangle& r) const { Rectangle u (max(xll, r.xll), max(yll, r.yll), min(xur, r.xur), min(yur, r.yur)); return u; } // Generate the Rectangle formed by extending one // edge of this one by one step in the indicated direction // (plus or minus dx, or plus or minus dy) //pre: dx == 0 || dy == 0; !(dx==0 && dy ==0) Rectangle Rectangle::extension (int dx, int dy) const { if (dx > 0) return Rectangle (xur+1, yll, xur+1, yur); else if (dx < 0) return Rectangle (xll-1, yll, xll-1, yur); else if (dy > 0) return Rectangle (xll, yur+1, xur, yur+1); else return Rectangle (xll, yll-1, xur, yll-1); } bool operator< (const Rectangle& left, const Rectangle& right) { if (left.xll < right.xll) return true; else if (left.xll > right.xll) return false; if (left.yll < right.yll) return true; else if (left.yll > right.yll) return false; if (left.xur < right.xur) return true; else if (left.xur > right.xur) return false; if (left.yur < right.yur) return true; return false; } ostream& operator<< (ostream& out, const Rectangle& r) { out << "[" << r.xll << " " << r.yll << " " << r.xur << " " << r.yur << "]"; return out; } // =========================================================================== class Picture { char* data; int nRows; int nCols; public: Picture (int numCols, int numRows); ~Picture(); Picture (const Picture&); const Picture& operator= (const Picture&); int numRows() const {return nRows;} int numCols() const {return nCols;} char& pixel (int col, int row) { return data[col * nRows + row]; } char pixel (int col, int row) const { return data[col * nRows + row]; } /** * Compute the smallest rectangle containing all pixels of * paper. */ Rectangle bounds(char paper) const; bool contains (const Rectangle& b, char paper) const; }; Picture::Picture (int nC, int nR) : nRows (nR), nCols (nC) { data = new char[nRows*nCols]; } Picture::Picture (const Picture& p) : nRows (p.nRows), nCols (p.nCols) { data = new char[nRows*nCols]; copy (p.data, p.data+nRows*nCols, data); } const Picture& Picture::operator= (const Picture& p) { if (this != &p) { delete [] data; nRows = p.nRows; nCols = p.nCols; data = new char[nRows*nCols]; copy (p.data, p.data+nRows*nCols, data); } return *this; } Picture::~Picture () { delete [] data; } ostream& operator<< (ostream& out, const Picture& p) { for (int r = 0; r < p.numRows(); ++r) { for (int c = 0; c < p.numCols(); ++c) out << p.pixel(c,r); out << endl; } return out; } istream& operator>> (istream& in, Picture& p) { for (int r = 0; r < p.numRows(); ++r) { for (int c = 0; c < p.numCols(); ++c) in >> p.pixel(c,r); } return in; } /** * Compute the smallest rectangle containing all pixels of * paper. */ Rectangle Picture::bounds(char paper) const { int xmin = nCols; int xmax = -1; int ymin = nRows; int ymax = -1; for (int r = 0; r < numRows(); ++r) for (int c = 0; c < numCols(); ++c) if (pixel(c,r) == paper) { xmin = min(xmin, c); xmax = max(xmax, c); ymin = min(ymin, r); ymax = max(ymax, r); } return Rectangle(xmin, ymin, xmax, ymax); } bool Picture::contains (const Rectangle& b, char paper) const { for (int c = max(b.xll, 0); c <= min(b.xur, nCols-1); ++c) for (int r = max(b.yll, 0); r <= min(b.yur, nRows-1); ++r) if (pixel(c,r) == paper) return true; return false; } // =========================================================================== /* * relations[x-'a'][y-'a']: * = 0 if we do not yet know whether x can lie under or over y * = +1 if y MUST lie on top of x */ int relations[26][26]; bool checkNewEdge (const Picture& p, char paper, int numPapers, const Rectangle& edge, const Rectangle& extendedFrom) { // This edge is valid if it contains // no '.' marks and no characters x such that current.paper // must lie on top of x. bool valid = !p.contains(edge, '.'); for (int i = 0; i < numPapers && valid; ++i) if (relations[i][paper-'a'] > 0) valid = !p.contains(edge,i+'a'); /*if (valid) cerr << edge << " is a valid extension of " << paper << endl;*/ return valid; } bool checkExtensions(const Picture& p, char paper, int numPapers, const Rectangle& current) { bool canExtend = false; if (current.xll > 0) { Rectangle extendedEdge = current.extension(-1, 0); canExtend = checkNewEdge (p, paper, numPapers, extendedEdge, current); } if (!canExtend && current.xur < p.numCols()-1) { Rectangle extendedEdge = current.extension(+1, 0); canExtend = checkNewEdge (p, paper, numPapers, extendedEdge, current); } if (!canExtend && current.yll > 0) { Rectangle extendedEdge = current.extension(0, -1); canExtend = checkNewEdge (p, paper, numPapers, extendedEdge, current); } if (!canExtend && current.yur < p.numRows()-1) { Rectangle extendedEdge = current.extension(0, +1); canExtend = checkNewEdge (p, paper, numPapers, extendedEdge, current); } return canExtend; } void checkVisibility (Picture& p, int numPapers) { for (int i = 0; i < 26; ++i) for (int j = 0; j < 26; ++j) relations[i][j] = 0; // 1: Get the bounding boxes for all papers //cerr << p << endl; Rectangle bbox[26]; for (int ipaper = 0; ipaper < numPapers; ++ipaper) bbox[ipaper] = p.bounds('a' + ipaper); // 2: If the bounding box of x contains the character y, then y must lie on top of x // and x may lie beneath y for (int i = 0; i < numPapers; ++i) { //cerr << "BBox of " << (char)('a'+i) << " is " << bbox[i] << endl; for (int j = 0; j < numPapers; ++j) if (i != j) { if (p.contains(bbox[i], 'a'+j)) { //cerr << "Phase 1: " << (char)('a'+j) << " must be on top of " << (char)('a'+i) <> numRows >> numCols; if (numRows == 0 && numRows == 0) return false; Picture p (numCols, numRows); in >> p; int numPapers = 0; for (int r = 0; r < p.numRows(); ++r) { for (int c = 0; c < p.numCols(); ++c) { int ch = p.pixel(c,r); if (ch != '.') { int k = 1 + ch - 'a'; if (k > numPapers) numPapers = k; } } } //cerr << p << endl; checkVisibility (p, numPapers); return true; } void spycam (istream& in) { bool finished = false; while (!finished) { finished = !processDataSet(in); } } int main (int argc, char** argv) { // Program should normally read from standard in. But // for debugging purposes, it is sometimes easier to // give a file name on the command line. if (argc > 1) { ifstream in (argv[1]); spycam (in); } else spycam(cin); return 0; }