| Author: | A. Baranov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
Young programmer Vasya is learning hardware design. He created his first graphics controller, which is only able to draw rectangles. Unfortunately, in some cases controller seems to output incorrect images. To help Vasya debug his controller, write a program which checks if a given image is possibly a valid output, or is definitely incorrect.
Consider the graphic scene consisting of colored rectangles with sides parallel to coordinate axes. Each rectangle has a unique color.
A scene is rendered into a bitmap by drawing rectangles one by one. Each rectangle overwrites parts of the scene drawn before it. So in the final bitmap some rectangles may be fully or partially hidden by rectangles rendered later.
Your program must, given the final bitmap state, determine whether there exists a scene which can, after correct rendering, result in this bitmap state.
Input file contains the bitmap, represented by a rectangular matrix of pixels, one row per line. Each row is represented by a string, where each character corresponds to one pixel. The color of pixel is defined by a character's ASCII code, in range from 32 to 126 inclusive.
Space (ASCII 32) corresponds to the background color and is not a color of any rectangle.
Note: When solving this problem in C++, it is recommended to read input data with fgets function for acceptable performance.
Output file must contain a single integer: 1 — if the scene exists; 0 — otherwise.
Resolution of the input image is no more than 4000 × 4000 pixels.
All input lines have same length.
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|