2015
02-21

Maple is a good techer

Recently, Mr. Maple feels it more and more boring to check the students’ homework, especially those with multiple choice questions. Then he emerges an idea of using computer to help him check the answers. So that Mr. Maple needs a program, which can recognize what letters the students filled in after the answer sheets are scanned into the computer.
So far, the answer sheets have been transfered into square-like patterns (refer to the sample), in which ‘X’ presents the painted pixel, and ‘.’ presents blank. It’s your turn to write a program for recognition. Go!
* Some details about the patterns:
1) The size of patterns is always 16 * 16.
2) Each pattern can have one and only one character.
3) The character belongs to {A, B, C, D}.
4) The written character won’t be too small.
5) The character may be distorted or rotated (a little).
6) Redundant pixels would turn up in a few cases.
7) Necessary pixels would be missing in a few cases.
8) It is guaranteed that all the test data can be easily judged by eye.

The first line contains the number T of testcases (1 ≤ T ≤ 50). Then T patterns below.
Note that there is a blank line between the patterns.

The first line contains the number T of testcases (1 ≤ T ≤ 50). Then T patterns below.
Note that there is a blank line between the patterns.

3
................
........X.......
.......XX.......
......X..X......
.....XX..X......
.....X...X......
....XX...X......
....X....X......
...X.....XX.....
...XXXXXXXXXX...
..XX......XX....
..XX.......X....
..XX.......XX...
..XX........X...
.XXX.X.......XX.
................

..X.............
................
......XXXXXX....
............X...
.....XX......XX.
.....X.......XXX
....XX........X.
....X.........X.
...X.....XX..X..
...XXXXXXXXX....
...X......XX.X..
..X...........X.
..X...........X.
..X.........XX..
.XXXXXXXXXXX....
................

................
................
................
.........XXX....
......X.........
...XX...........
.XX.............
X...............
X...............
.XX.............
.XX.........X...
...XX.XXXXXXX...
.....XXXXXXX....
................
................
................

A
B
C

1. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环