1374 . AR Game
Description
Gamebox is developing a new augmented reality game for young kids. Players interact with the virtual object on screen through movements of markers. A marker is a square playing card with special
marking. Markers all have different markings. The game is played by showing a marker to the game console. The game console has a hidden video camera that can automatically locate and take a snapshot
of the marker being played. Depending on how the card is being held and the distance from the game
console, the captured image of the marker maybe displaced from the upright position. Furthermore,
noise may be introduced during the imaging process. The marker is then recognized and the game is
played accordingly. Obviously, if the marker were incorrectly recognized, then the game would not be
played correctly. You are hired as a game programmer to make sure that the markers are recognized
correctly.
Input Format
The input file contains a set of test images. Each test image is defined by a single integer n on one line
to indicate the image size (nxn). This number is either 0, 50, 100, 150, or 200. 0 indicates the end of
the test data. This is followed by n rows of n consecutive 0s and 1s, which defines the captured image
to be processed.
Constraints
1. All the images are binary images (containing only two colors: black and white). 0 denotes black
pixel and 1 denotes white pixel.
2. There are 5 markers. Each has been digitized into a 100x100 image. The images are shown and
described below in graphical form.
3. The captured image (test images) can be
• Rotated: in 0, 90, 180, or 270 degree angle.
• Enlarged/shrunk: image size can be of size 50x50, 100x100, 150x150, or 200x200.
• Contains random noise: at most 3% of the pixels in the input image are reverted. Black
becomes white or vise versa.
• Any combination of the above conditions.
Output Format
For each input case, output a single integer on one line indicating the marker that matches with the
given input image.
Sample Input 1
50 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11100000000000000000000000000000000000000000000111 11100000000000000000000000000000000000000000000111 11100111111111111111111111111111111111111111100111 11100111111111111111111111111111111111111111100111 11100111111111111111111111111111111111111111100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111110000000000011100111 11100111111111111111111111111111111111111111100111 11100111111111111111111111111111111111111111100111 11100111111111111111111111111111111111111111100111 11100000000000000000000000000000000000000000000111 11100000000000000000000000000000000000000000000111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 50 11111111111111111111111011111111111111111111110111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11100000000000000001000000000000000000000000000111 11101000000000000000000000000000000000000000000111 11100111111111111111111111101111111111111111100111 11100111111111111111111111111111110111111101100111 11100111111111111111111111111111111110111111100111 11100111000000000000000000000000001111111111100111 11100111000000000000000000000010001111101111100110 11100111000000000000000000000000001111111111100111 11100111000001000000000000000000001111111111100111 11100111000000010000000010000000001111111111100111 11100111000000000000000010000000001111111011100101 11100111000000000000000000001000001111111111100111 11100111000000001000000000000000001111111110100111 11100011000000000000000000000000000000000011100111 01100101000000000100000000000000000000000011100111 11100111000000000000010000000000000000000011100111 10100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000001011100110 01100111000001000000010000000000000000100011100111 11100111000000000000000000000001000000100011100111 11100111000000000000000000000000000010000011100111 11100111000000000000000000000000100010000011110111 11100111000000000000000000000100000000000011100111 11100111000000000000000000000000000000000011100111 11100101000000000000000000000000000000010011100111 11100111000000000000000000000100000000000011110111 11100111011000000000000000000000000000000011100111 11100111000001000000000000000000000000000011100111 11100101000000000000000000000000001000000011100111 11100111000000000000000000000000000000000011000111 11100111000000000000000010000010000000001011100111 10100111000000010000000000000000000000000011100111 11100111000100100000000000000000000000000011100111 11100101010001000000000000000000000000000001100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000000000000000000000000000000011100111 11100111000000100100000000000000000000000011100111 11100111000000000000001000000000000000000011100111 11100111111111101111111111111111111111111111100111 11100111111110111111111111111110101111111111100111 11100111111101111111111111111111110111111111100111 11100000000000000000000000000000000001000000000111 11100000000000000000000000000010000000000000000111 10111111111111111111111111111111111111111111111111 11111111111111111111111111111111111101111111111111 11111111111111111111111111111111111111111111111111 0
Sample Output 1
3 5
Hints
Problem Source
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Kaohsiung
Subtasks
| No. | Testdata Range | Score |
|---|