Time Limit: 2 Seconds
Memory Limit: 65536 KB
Recently DZB is playing a game called Dot Dot Dot. It's a simple game but very interesting. The rule is like this:
The game is played on a N*M grid map, each grid is adjacent with 4 grids(up, down, left, right). There's only one exit on the map, the game finished when the player reach the exit. When the game starts, the player go to the exit step by step. In each step he can only move to adjacent grid. But there's some barriers on the map, each barrier is yellow or green. The player can not go to the grid when there is a barrier or there is outside wall.
The only way to destroy the barriers is to stand on some grid which has a trigger. Each trigger is also yellow or green and can be used only once. When the player stand on it, it will sent shock waves to destroy all the barriers with the same color it could reach directly. Shock waves spread as wide as possible. It can spread on all the connected grids which no barrier is on it, that means if it reach a barrier with different color, it will be blocked too. Notice if the wave can not reach a barrier directly, it can not be destroied, even if it's the same color with the trigger.
Now DZB not only wants to finish the game, but also wants to finish the game with the minimal step, so he ask you for help.
There are multiple test cases. For each test case:
The first line contains two integers N(1≤N≤40), M(1≤M≤40), N is the number of rows of the map, and M is the number of the columns.
The after N lines describe the map, each line has M characters. A character could be:
There is a blank line between every two cases.
Process to the end of input.
5 17 ***************** *.......Y.......* *.y.s...Y....e..* *.......Y.......* *****************