Patkice
레이팅 미적용의견: 0
Not so long ago, in a distant tropical land, there lived three rubber ducks. One hot summer day while they
were lying on the beach, the ducks decided to travel to a nearby island. Since the ducks like adventures,
they decided to travel carried by ocean currents in an old black umbrella.
Since the ducks are experienced ocean explorers, before the voyage they will check out a map of ocean
currents. On the map, the island where the ducks live is marked by a letter ’o’. The ducks can start
their voyage in any of the four directions: north – N, east – E, west – W and south – S.
Ocean currents in these seas move in one of the four directions, and are marked on the map in the following
way: we\(st-ea\)st ’<’, ea\(st-we\)st ’>’, nor\(th-so\)uth ’v’ and sou\(th-no\)rth ’^’. When the ducks are located on
a cell with a current, they will move one cell in the direction of the current. Ocean currents in these seas
are special, as they never lead outside of the map and they don’t form vortexes (places where the ducks
would move in circles if they followed the current).
Calm sea is marked by a dot ’.’. If the currents bring the ducks to a cell with calm sea or back to the
starting island, they won’t be able to continue the voyage. The island that the ducks want to visit is
marked by a letter ’x’.
The ducks don’t want to stop their beach party. They kindly ask you to tell them if it’s possible for them
to get to the other island, and if it is, in which direction should they start their voyage. Since one of
the ducks gets very seasick, they ask you to choose the direction that will make the voyage as short as
possible. If there are multiple directions that yield the same minimal travel time, you should choose the
one that is alphabetically first.
In test cases worth 30 points the valid start direction will be unique if it exists.
The first line contains integers \(r\) and \(s\) (\(3 \le r\), \(s \le 100\)), the number of rows and columns of the map.
Each of the next \(r\) lines contains \(s\) characters from the set ’o<>v^.x’, that represent the map of ocean
currents. There will always be exactly one character ’o’ and exactly one character ’x’ on the map. The
character ’o’ will never be located in the first or last row nor column.
If the ducks can’t reach the other island, print :(.
Otherwise, print :) in the first line. In the second line, print the start direction (N for north, E for east, W
for west or S for south).
6 6
..>>>v
.o^..v
.v.<.v
.>>^.v
.x<<<<
......
:)
E
5 5
v<<<<
>v.>^
v<.o.
>>v>v
..>>x
:)
S
3 3
x>.
.o^
^<.
:(
평가 및 의견
Patkice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Patkice