← 返回题目列表

Codeforces · 793/B

B. 伊戈尔和他的工作方式

中文机器翻译题面 查看原题

金融分析师伊戈尔被闹钟吵醒,赶紧开始工作。他吃完早餐,坐进车里。遗憾的是,当他打开GPS导航仪时,发现自己居住的城市Bankopolis的部分道路因道路施工而封闭。此外,伊戈尔的方向盘有些问题,所以他在去银行办公室的路上最多只能转两圈。

Bankopolis 看起来像一个 n 行 m 列的网格。伊戈尔应该找到一条从家到银行的路,转弯不超过两个,并且不包含道路施工的单元格,或者确定这是不可能的,他应该在家工作。转弯是运动方向的改变。伊戈尔的车只能向左、向右、向上和向下移动。最初伊戈尔可以选择任何方向。伊戈尔还很困,所以你应该帮助他。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) — 网格中的行数和列数。

接下来的 n 行中的每一行都包含 m 个字符,表示网格的相应行。可能出现以下字符:

- “。” — 一个空单元格;
- “*” — 有道路工程的单元格;
- “S” — Igor 家所在的小区;
- “T” — Igor 办公室所在的牢房。

保证“S”和“T”各恰好出现一次。

输出

如果 Igor 的家和 Igor 的办公室之间有不超过两圈的路径,则在唯一的行中打印“YES”,否则打印“NO”。

示例

输入 #1

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

输出 #1

YES

输入 #2

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

输出 #2

NO

注意

第一个示例如下图所示:

在第二个示例中,不可能使用少于 4 个转弯到达 Igor 的办公室,因此不存在使用不超过 2 个转弯的路径。恰好使用 4 个转弯的路径如下图所示: