Romance of The Three Kingdom (acm15_three_kingdom)


Time limit:
1000 ms
Memory limit:
32 MB

In Han dynasty, Chinese is divided to three kingdom: Cao Wei (by Cao Cao),
Shu Han (by Liu Bei) and Dong Wu (by Sun Quan). After that, Chinese is merged in one kingdom. In this task, same kingdom is connected in 4 directions: up, down, left and right.

Chinese has R row C column which '.' is sea, 'X' (Greater X) is land. e.g. R=6,
C=14 shown

Left image is Chinese land initiation

Middle image describes name of each kingdom

Right image is new Chinese kingdom that cover 2 sea blocks to connect three
kingdom.

Write program to find minimum sea block to cover for connect three kingdom.

Input

First line integer Q (Q <= 15), number of question. Each question

First line integer R C separated with blank space (1 <= R, C <= 50)

Next R line input Chinese map which '.' is sea, 'X' (Greater X) is land.

Guarantee input map has exactly three kingdom.

Output

Q line each line show minimum sea block to cover for connect three kingdom.

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None