| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 101 | 79 | 72 | 78.261% |
Plot a path through the asteroid field. Given a starting location, final destination, and a description of the asteroid fields plot a shortest path that takes you from the starting location to the final destination without running into any asteroids. The asteroid field is described using a mxm grid of characters with
Here is an example of a 4x4 grid.
s*-* -*-* ---- *-*d
Your ship can move up, down, left, and right (not diagonally). Each position in a mxm grid will be assigned an integer between 0 and m2-1 as follows.
The first line will have a positive integer n representing the number of data sets. The first line of each data set will contain an integer m, followed by m lines, and each line will contain m characters. The character s will always be in the top left corner and d will always be in the bottom right corner.
For each data set print the minimal number of moves needed to reach the destination or -1 if there is no solution.
2 4 s*-* -*-* --*- *-*d 6 s*---* -*-*-- ---**- ***--- --*-** *-*--d
-1 18