| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 168 | 137 | 115 | 80.986% |
ou are surrounded by Imperial warships and must land on a planet to escape. Your best chance is to find a route to the closest planet. Unfortunately the navigation system has been damaged. Your job is to write a program that will find the planet that is closest to your current location. The problem will be described using a mxm grid containing the characters
The two dimensional location of an object (i.e., your ship, imperial warship, or planet) corresponds to its location in the grid. For example given a 4x4 grid the locations are specified by the following table.
Recall that the distance between two points (x1, y1) and (x2, y2) is given by the formula
dist = ( (x1 - x2)2 + (y1 - y2)2 )1/2
The first line will have a positive integer, n, specifying the number of data sets to follow. Each data set will have a positive integer, m, on the first line followed by m lines and each line will have exactly m characters. The characters will be either s, w, p, or -.
For each data set print one line with the coordinates of your current location followed by a colon, coordinates of a closest planet followed by a colon, and the distance to that planet formatted to two decimal places.
2 4 -wp- s--w -w-p -pw- 5 s--wp w--pw -w-p- p--wp w--pw
(1,0):(0,2):2.24 (0,0):(3,0):3.00