You have a treasure map that is arranged into a N * M grid. A grid square may be either sea or part of
an island. In addition, the map shows the treasure and an enemy Viking ship that occupies one (sea)
square. Finally, for convenience you have also drawn your own position.
Now you must set up a fixed route to get the treasure. The route must start at your position, end at
the treasure, and consist of a sequence of moves. In each move, you can go only to an (horizontally
or vertically) adjacent square that is not part of an island. But beware: The Viking ship might follow
you, using the same kind of moves! After each of your moves according to your route, the Viking
ship may move or not. Your move and the Vikings' reaction together is called a round.
After every round, the following checks are made:
The first line of input contains two integers N and M, the dimensions of the map. Each of the
following N lines contain M characters. Each character describes a square in the map, and is either
. (sea), I (part of an island), V (the Viking ship), Y (your position), or T (the treasure). Each of V, Y,
and T will occur exactly once.
1 ≦ N, M ≦ 700
The only line of the output must contain the string YES, if it is possible to set up a route to get the
treasure, or NO otherwise.
5 7 Y.....V ..I.... ..IIIII ....... ...T... 5 7 Y....V. ..I.... ..IIIII ....... ...T... 2 3 .YT VII
YES NO NO
In the first example, the following route will let you get the treasure:
Down, Down, Down, Right, Right, Right, Down.
In the second and third examples, there is no route to the treasure that you will survive.
Migrated from old NTUJ.
BOI2011 Competition Day 1
| No. | Testdata Range | Score |
|---|