Need some help with another algorithmic problem.

Nineshadow · March 12, 2016

@fizzlesticks Yet another space traversal problem.

In a city there are k friends who want to attend a demonstraiton in their rather big neighbourhood , so they decided they are going by car. Also , every person will carry with them a placard , which has a big letter drawn on it ( A, B , ... , Z) .
There are no placards with identical letters. The k letters end up forming a word, which is given in the input.

The neighbourhood can be represented by a n*m matrix which has some areas which the friends cannot go through. In the input file , these are noted with '#' , while the cells which they can go through are noted with '_'. It is known that a car uses 1 unit of fuel to go from one cell to another adjacent one. A cell is adjacent to another one if they share one side.

To conserve fuel , they decide that if two cars find themselves in the same cell , and the letters in those cars represent a sequence of the given word, then they will continue their journey with only a single car. If the letters do not make up a sequence of the given word , then they continue their journey separately. For example , let's consider the word "DOWN". A car carrying the letter 'D' can take in a person carrying the letter 'O' .. So the people carrying 'D' and 'O' will join together into a single car. Let's say that 'W' and 'N' also meet, and they will be in a single car as well. After that , the two cars meet, one carrying "DO" , and the other "WN", and end up making the word "DOWN".

You are required to find out the minimum units of fuel consumed by all the cars so that all friends end up in a single car. If they cannot all meet in a single car, then the output will be -1.

Input is structured as follows :

n , m

WORD

The n*m matrix , made out of big letters ('A' ... 'z') , '_' AND '#';

Example :

Input :

5 7
LOW
_#_#_#_
__L#__#
_#__O__
W__#_#_
_#_#_#_

Output: 6

A minimum path is this :

Input :

6 7
DOWN
D#_#_#_
___#__#
_#_O___
____#__
__#_W_#
_#_N_#_

Output : 9

A minimum path can look like this :

Restrictions :

n,m <= 60

k<=10

time : 1 sec

memory : 16 MB

I got this problem in a contest today. I got 45% just by doing a lee algorithm for each letter in turn , then finding out the intersection of the paths of all the letters with the minimum fuel cost. It totally ignored the mechanic of merging into a single car , so I'm pretty surprised I got that much. Luckily , nobody else did a better job than me so I guess I should be pretty happy. Anyway , time to figure out how it's really done.