TANDV - Treasures and Vikings

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:

  • If you are in line with the Viking ship (you are in the same vertical or horizontal line as the Viking ship with only sea between the Viking ship and you), you are dead.
  • If you aren’t dead and at the treasure-spot, you get the treasure.

Write a program that decides whether it is possible to set up a fixed route in advance such that you can get the treasure by following this route and will not get killed by the Vikings – no matter how the Viking ship moves.

Input

The first line of input contains two integers N and M (1 <= N, M <= 700), 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.

Output

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.

Example

Input:
5 7
Y.....V
..I....
..IIIII
.......
...T...

Output:
YES

Được gửi lên bởi:bnta2
Ngày:2011-11-28
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP D FSHARP JAVA PAS-GPC PAS-FPC PYTHON PYTHON3
Nguồn bài:BOI

hide comments
2011-12-01 17:24:48 TLMN
Bài này hình như test hơi yếu thì phải, mình chạy nhiều test đơn giản vẫn sai mà sub lại AC :|


Last edit: 2011-12-02 05:11:57
2011-11-29 00:57:26 Gr Sven
Chuyển sang ACM rồi :))
2011-11-28 23:58:59 [midfinger]
Random kết quả cũng đk ối điểm nhey .. :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.