1225 - Help!
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 8
Solved: 3
- Description
- Long long ago, there was a rectangular land divided into N*M square fields. Some of them were filled with water, so anyone can’t pass by the water fields. An old man Xiangsanzi lived in this land. One year, an earthquake happened there, and the pitiful guy Xiangsanzi was in danger. Fortunately, two persons, Sempr and Acman tried to rescue Xiangsanzi, and they knew there was a magic door (we can call it magicD) which connected another land and its key in this land. So their aim was to get the key and find Xiangsanzi, then they three arrived at the magicD to escape. Sempr and Acman could do those things separately or together.
As we know, in the field land, one could only move to one of four adjacent field and go across one field in one minute.
- Input
- The first line is a number T which refers to the test cases.
For each case, the first line are two integer N, M (2<N, M<100), which represent the number of person in the group.
Then follow M lines, containing a string whose length is m in each line, describe the field. The char ‘w’ means the field is filled water. ‘l’ means is it land. ‘b’ means where are Sempr and Acman are now. ‘x’ means where are Xiangsanzi now. ‘k’ means the key is at that place and ‘d’ means magicD, and there is no other char in the input. The chars appear and only appear once except ‘w’ and ‘l’. You can pass by any field except ‘w’.
- Output
- Output the least minutes for the three to escape. If they can’t escape, output -1.And one line for each case
- sample input
-
2 2 2 bx kd 3 3 Blx lwl kld
- sample output
-
2 4
- hint
- source
- Xiangsanzi, HUST Programming Contest 2007