The map is a 2-dimensional grid of squares, each square is filled with one color. You will be given a sequence of colors. You can move between adjacent squares vertically or horizontally in the given color order. '*' is where you start, and '#' is the goal.
For example, given the map as follow, and the color order "RGB":
BGRG#
RGBGR
*GRGB
There are two different ways to reach the goal:
xx456
123xx
0xxxx
and
xxxx8
123x7
0x456
So we know that the shortest path from '*' to '#' needs 6 steps.
Implement a BFS to find the smallest number of steps to reach the goal.
The input consists of several maps. Each map begins with a line containing two integers N and M (1 <= N, M <= 10^3) specifying the map height and width. The next N lines will be M upper case letters, '*', or '#'. Each letter denotes one color.
The next line is a string that specifies the color order. One color won’t appear twice in the given order.
Each case is separated by a blank line. The input is terminated by two zeros.
For each map, print one line containing the smallest possible number of step to reach the goal. If there's no way to reach the goal, output the string "No solution." instead. One step is defined as a movement between two adjacent cells.