|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
A popular solitaire board game is played on a rectangular m × n game board consisting of mn squares. The board initially comes entirely populated with either animals or obstacles. An ‘X’ in a square denotes an obstacle, a digit ‘0’–‘9’ in a square denotes the species of the animal.
Pairs of animals can only be removed if they are of the same species. If a pair of animals are removed, the squares in which they were located become empty and stay empty for the rest of the game. To be removed, a candidate pair must either be adjacent to each other or have a path between them. Two squares are adjacent if they are side by side horizontally or vertically. A path is a sequence of adjacent empty squares. The path length of a path is simply the number of empty squares in the path.
You should output the maximal number of pairs of animals it can remove from the board and the minimal cumulative path length needed to achieve this.
The first line of the input file contains the integers m and n separated by a space, 1 ≤ m ≤ 5, 1 ≤ n ≤ 5. Each of the subsequent m lines contains n characters, each character is one of ‘X’, ‘0’, ‘1’, · · ·, ‘9’. There is no space between adjacent characters.
The output file contains two integers separated by a space. The first integer is the maximal number of pairs of animals that can be removed. The second integer is the minimal cumulative path length needed to achieve the maximal number of pairs.
3 4 XX0X X11X X0XX
The two animals of species 1 can be removed because they are adjacent and the path length between them is 0. After their removal, there is a path of length 2 between the two animals of species 0, thus these two animals can be removed too. To remove these two pairs of animals, the cumulative path length is 0 + 2 = 2. This is also the minimal cumulative path length as there is only one way to remove both pairs of animals. Thus the answer is 2 2.
4 1 9 9 9 9
If we first remove the two middle animals of species 9 and then remove the top and bottom animals of species 9, two pairs of animals are removed with a cumulative path length 0 + 2 = 2.
But we can remove the top two animals of species 9 and then remove the bottom two animals of species 9. This also removes two pairs of animals with a cumulative path length 0 + 0 = 0.
Clearly a zero cumulative path length is minimal. Thus the answer is 2 0.