Igor and his way to work

题意翻译

### 题目描述 伴随着闹钟的铃声，财政分析家$Igor$匆忙起来赶去工作。他吃完早餐后就做到了他的车上。不幸的，当他打开他的$GPS$导航时，发现在他所居住的小镇$Bankopolis$中的一些道路，由于道路施工而关闭。更不幸的是，车的方向盘有点问题，所以在他去他的银行办公室的途中，**最多转两次弯** --- 小镇$Bankopolis$可以看做是一个$n$行$m$列的网格图 ,$Igor$需要找到一条从家到银行的道路，这条道路转弯次数最多为$2$次，且不能经过正在维修的道路，或者你可以告诉他不能到达，他应该在家工作。一个**转弯**的定义是：`$Igor$的车改变一次方向`。$Igor$的车只能向**上，下，左，右**四个方向行驶。在最开始的时候，$Igor$的车可以选择任何方向。因为$Igor$仍然在睡觉，所以你应该帮帮他 ### 输入输出格式 #### 输入格式 第一行包含两个正整数$n$和$m$表示$Bankopolis$小镇的行数和列数 接下来$n$行，每行$m$个字符，用于描述一个$n \ * \ m$的矩阵 可能会出现以下字符： ".":$ \ \ $一个可行的道路 "\*":$ \ \ $正在施工的道路 "S":$ \ \ $ $Lgor$的家 "T":$ \ \ $ 银行办公室的位置 **保证$S$和$T$有且只出现一次** #### 输出格式 如果能够到达，输出`YES`否则输出`NO` Translated by @Chloristendika

题目描述

Woken up by the alarm clock Igor the financial analyst hurried up to the work. He ate his breakfast and sat in his car. Sadly, when he opened his GPS navigator, he found that some of the roads in Bankopolis, the city where he lives, are closed due to road works. Moreover, Igor has some problems with the steering wheel, so he can make no more than two turns on his way to his office in bank. Bankopolis looks like a grid of $ n $ rows and $ m $ columns. Igor should find a way from his home to the bank that has no more than two turns and doesn't contain cells with road works, or determine that it is impossible and he should work from home. A turn is a change in movement direction. Igor's car can only move to the left, to the right, upwards and downwards. Initially Igor can choose any direction. Igor is still sleepy, so you should help him.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=1000 $ ) — the number of rows and the number of columns in the grid. Each of the next $ n $ lines contains $ m $ characters denoting the corresponding row of the grid. The following characters can occur: - "." — an empty cell; - "\*" — a cell with road works; - "S" — the cell where Igor's home is located; - "T" — the cell where Igor's office is located. It is guaranteed that "S" and "T" appear exactly once each.

输出格式

In the only line print "YES" if there is a path between Igor's home and Igor's office with no more than two turns, and "NO" otherwise.

输入输出样例

输入样例 #1

5 5
..S..
****.
T....
****.
.....

输出样例 #1

YES

输入样例 #2

5 5
S....
****.
.....
.****
..T..

输出样例 #2

NO

说明

The first sample is shown on the following picture: In the second sample it is impossible to reach Igor's office using less that $ 4 $ turns, thus there exists no path using no more than $ 2 $ turns. The path using exactly $ 4 $ turns is shown on this picture: