|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||8||1||1||33.333%|
Since IDI Open ’09, I’ve had lots of sheep counting programs supposed to help me fall asleep. Sadly, none of these were any good, so I’ve spent close to every night the last years cursing those evil animals. Not sleeping gives you quite a bit of spare time, and I’ve spent mine creating a new game called Sheep Frenzy.
The player controls Ulgr the Unpleasantsmelling, whose objective is to eat all sheep on each level as fast as possible. Strangely enough, though I’ve gotten quite good at it, this still doesn’t give me the satisfaction of revenge on the evildoers. This is why I need your help. You need to write a program that calculates the best way of moving Ulgr around the board in order to eat all sheep as fast as possible.
The board is organized in a H × W grid, where each cell is one of the following:
Ulgr makes one move each second. One move consists in eating a sheep or moving one cell to the left, right, up or down. He can only eat a sheep if he stands on the same cell as it.
The first line of input contains a single number T, the number of test cases to follow. Each test case begins with a line containing two numbers, H and W, the height and width of the grid for that level. Then follow H lines, each containing W characters, describing that part of the grid.
For each test case, output a line containing a single number, the minimum time in seconds Ulgr needs to eat all the sheep on that level. If it is not possible to eat all the sheep, output impossible instead.
2 2 2 U. .# 3 5 #..X# ..XXX .U...