Romance of The Three Kingdom (acm15_three_kingdom)

• Problem
• Submit
• Status
• Discussion
• Solution
• Analytics

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