I.bad friends
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
HH,LL and TT are three bad friends. But their houses are very near from each other. They want to put some barriers so that their houses couldn't connect together.
"H" on the map indicates HH's house,"L" indicates LL's house ,"T" indicates TT's house,"." indicates free space and you could put a barrier on it. ."X" indicate a barrier.
If there are three or more free spaces connect to one's house,the house is not save. No one will live on an unsave house.And I sure the three boys must live on save houses.
Now, tell you the information of the map, please help the three Poor boys to calculate the minimum barriers they need to put so that their houses couldn't connect together.
"H" on the map indicates HH's house,"L" indicates LL's house ,"T" indicates TT's house,"." indicates free space and you could put a barrier on it. ."X" indicate a barrier.
If there are three or more free spaces connect to one's house,the house is not save. No one will live on an unsave house.And I sure the three boys must live on save houses.
Now, tell you the information of the map, please help the three Poor boys to calculate the minimum barriers they need to put so that their houses couldn't connect together.
Input
The first line with two numbers n and m(0<n,m<10) stands for the size of the map;then n lines follow ,each line with m characters.There are exact one "H",one "L" and one "T".
And I ensure the number of "X" will not exceed 5.
There are no more then 30 cases.
A blank line after each test case.
And I ensure the number of "X" will not exceed 5.
There are no more then 30 cases.
A blank line after each test case.
Output
Output the minimum barriers they need to put.If there is no way to separate them ,just output "Impossible".
Sample Input
5 5 ..... H.... XX.XX ..... .LXT. 3 5 LX.X. ..HT. .XXX.
Sample Output
1 Impossible
Author
Source
Developing School's Contest 6