| Problem C: Matrix World |
Yes, The Matrix exists! Actually, it existed much before, but people started thinking about it only after the mega movie The Matrix. Nowadays, lot of people go out of the Matrix into the real world, mainly to collect diamond treasures. After spending lot of time in front of the computer, you decide to take a break and go into the real world. The real world has lot of radar stations to locate the objects and you plan to attack one of those radar stations to get a nice idea of the region. The radar stations show a map of the nearby area which follows the legend given below.
'*' - Diamond Treasure
'.' - Empty Cell
'#' - Forbidden Rock Cell
'X' - Guard Machines
'O' - Your Current Position.
Of course the Guard Machines will sense your arrival and start moving. You estimate that you will take exactly one second to move from one cell to another. Collecting one diamond treasure will also take exactly one second. The Guard Machines also move at one cell per second. Of course, you wish to collect the maximum number of diamond treasures (don't you ?). If there are several ways to collect the maximum number of treasures, you want to do it in the fastest time possible. The region shown on the radar is fenced and protected from outside. So, you cannot go out of the region and no Guard Machine can come into it.
Write a program which computes the minimum time to collect the maximum number of treasures from the real world given the map of the region.
Input consists of several test cases. Each test case begins with a line containing two integers M and N which specify the size of the map, 2£ N, M£ 30. Next M lines give N characters that describe the map itself. Each of the maps in the input follow the legend given above. The number of diamond treasures in a map is limited to 10.
For each test case in input, first print the line "Case t:" where t is the case number starting from 1. If it is not possible to collect any treasures from the real world, print the line "No treasures can be collected.". Otherwise, print the line "Maximum number of collectible treasures: max." where max is the maximum number of treasures that can be collected from the region without being terminated by the Guard Machines. If a Guard Machine can reach a cell at the same time you finish collecting a treasure, that treasure should not be counted as collected because you need some time to escape from the real world. In the next line, print the line "Minimum Time: min sec." where min is the minimum time required to collect max treasures. Print a blank line after every test case.
5 5 ....X .#### ...*# #*..# #..O# 4 3 O** *.. ##. X.. 4 3 .O. *.. ##X X.. 3 3 ##* .O. *#*
Case 1: Maximum number of collectible treasures: 2. Minimum Time: 7 sec. Case 2: Maximum number of collectible treasures: 2. Minimum Time: 4 sec. Case 3: No treasures can be collected. Case 4: Maximum number of collectible treasures: 3. Minimum Time: 11 sec.