Mr and Mrs Ant
All submissions for this problem are available.
Mr. and Mrs. Ant are very hungry. So, they want to collect food as much as they can. They can search for foods simultaneously. To do so, they start from their house and collect all foods together and meet in some place (not necessarily their house). Finally, they eat together.
The world of Mr. and Mrs. Ant is a two dimensional grid. Each cell is either the home, or free, or blocked, or contains a food. Two cells are adjacent if they share an edge. In each second, they can move from one cell to another cell simultaneously. One can decide to not to move in some step, while other may move. One cell can be visited many times. Both of them can move into the same cell also.
In this problem, the grid is given by an R x C matrix represented by following characters:
|H||Home of Mr. and Mrs. Ant||Occurs exactly once|
|F||A food item||Occurs at least once, at most 8 times|
|. (dot)||Free (passable) cell||-|
|# (hash)||Blocked Cell||-|
Given the grid information, give the minimum amount of time that must be needed for them to collect all the foods and then meet.
The first line of input will contain T (T <= 30) denoting the number of cases. Each case starts with two integers R and C (2 <= R, C <= 12). Then, R lines follow giving the grid.
For each case, print the case number, the minimum amount of time (in seconds) that must be needed for them to collect all the foods and meet. If it is impossible to collect all the food items, output -1 (negative one) instead.
Input: 2 2 3 H#. .#F 2 6 F#F..# ..H#.F Output: Case 1: -1 Case 2: 8
|Time Limit:||0.972289 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.