Problem C. Correctness of controller

Author:A. Baranov
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

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 format

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 format

Output file must contain a single integer: 1 — if the scene exists; 0 — otherwise.

Constraints

Resolution of the input image is no more than 4000 × 4000 pixels.

All input lines have same length.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
   *******               @@@@@@@
   *******      ######## @@@@@@@
   *******bbbbb //////// @@@@@@@
          bbbbb //////// @@@@@@@
yy   .....bbbbb ////////        
yy   .....      ########        
yy   .....      ########00000   
yy   .....      ########00000   
                ########00000   
ttttxxxxxxxxxxx     000000000   
ttttxxxxxxxxxxx ====000000000===
ttttUUUUUUxxxxx ====000000000===
    UUUUUUxxxxx ====000000000===
    UUUUUUxxxxx ====000000000===
    UUUUUU      ================
    UUUUUU                      
1
2
xxxx       xxxxxxxx@@@@@@@@@    
xxxx  aaa  xxxxxxxx@@@@@@@@@    
xxxx       xxxxxxxx@@@@@@@@@    
xxxx  xxx                xxxxxxx
xxxx  xxx                xxxxxxx
xxxx       xxxxxxxx      #######
xxxx    ===xx======   xxx#######
xxxx    ===xx======   xxx#######
xxxx    ===xx======   xxx///////
xxxx    ===xxxxxxxx   xxx///////
        ===========      ///////
    xxxx===========      xxxxxxx
    xxxx===========      xxxxxxx
    xxxx===========      xxxxxxx
    xxxxxxxxxxxxxxxxxxxx        
    xxxxxxxxxxxxxxxxxxxx        
0

0.020s 0.007s 9