B. Igor and his way to work

Codeforces
IDCF793B
Time3000ms
Memory256MB
Difficulty
dfs and similargraphsimplementationshortest paths
English · Original
Chinese · Translation
Formal · Original
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. ## Input 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. ## Output 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. [samples] ## Note The first sample is shown on the following picture: <center>![image](https://espresso.codeforces.com/e75f3583a07c0c822b88dee678d8262dff698f6b.png)</center>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: <center>![image](https://espresso.codeforces.com/b71c8ff0a0b6e016593fc67072608139d81966a8.png)</center>
被闹钟吵醒后,金融分析师 Igor 急匆匆赶往工作地点。他吃完早餐,坐进车里。可惜的是,当他打开 GPS 导航时,发现他所居住的城市 Bankopolis 的一些道路因施工而封闭。此外,Igor 的方向盘有问题,因此他在前往银行的路上最多只能转弯两次。 Bankopolis 呈现为一个 #cf_span[n] 行 #cf_span[m] 列的网格。Igor 需要找到一条从家到银行的路径,该路径最多包含两次转弯,且不经过任何有施工的道路单元格;若不存在这样的路径,则他只能在家工作。转弯定义为移动方向的改变。Igor 的车只能向左、右、上、下四个方向移动。初始时,Igor 可以选择任意方向。Igor 仍然昏昏欲睡,因此请你帮助他。 第一行包含两个整数 #cf_span[n] 和 #cf_span[m](#cf_span[1 ≤ n, m ≤ 1000]),分别表示网格的行数和列数。 接下来的 #cf_span[n] 行,每行包含 #cf_span[m] 个字符,表示网格的对应行。可能出现的字符如下: 保证 "_S_" 和 "_T_" 各恰好出现一次。 仅输出一行:如果存在一条从 Igor 的家到办公室、且转弯次数不超过两次的路径,则输出 "_YES_";否则输出 "_NO_"。 第一个样例如下图所示: 在第二个样例中,无法用少于 #cf_span[4] 次转弯到达 Igor 的办公室,因此不存在转弯次数不超过 #cf_span[2] 的路径。恰好使用 #cf_span[4] 次转弯的路径如下图所示: ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m](#cf_span[1 ≤ n, m ≤ 1000]),分别表示网格的行数和列数。接下来的 #cf_span[n] 行,每行包含 #cf_span[m] 个字符,表示网格的对应行。可能出现的字符如下: "_._" — 空单元格; "_*_" — 有施工的道路单元格; "_S_" — Igor 家所在的单元格; "_T_" — Igor 办公室所在的单元格。 保证 "_S_" 和 "_T_" 各恰好出现一次。 ## Output 仅输出一行:如果存在一条从 Igor 的家到办公室、且转弯次数不超过两次的路径,则输出 "_YES_";否则输出 "_NO_"。 [samples] ## Note 第一个样例如下图所示: 在第二个样例中,无法用少于 #cf_span[4] 次转弯到达 Igor 的办公室,因此不存在转弯次数不超过 #cf_span[2] 的路径。恰好使用 #cf_span[4] 次转弯的路径如下图所示:
**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the dimensions of the grid. Let $ G \in \{ \text{'.', 'X', 'S', 'T'} \}^{n \times m} $ be the grid, where: - `'.'` denotes an open cell, - `'X'` denotes a blocked cell (road work), - `'S'` denotes the unique start position, - `'T'` denotes the unique target position. Let $ s = (r_s, c_s) \in \{1, \dots, n\} \times \{1, \dots, m\} $ be the coordinates of `'S'`. Let $ t = (r_t, c_t) \in \{1, \dots, n\} \times \{1, \dots, m\} $ be the coordinates of `'T'`. A *path* is a sequence of adjacent (up/down/left/right) open cells from $ s $ to $ t $, avoiding `'X'`. A *turn* is a change in the direction of movement between two consecutive steps (e.g., from right to down). The initial direction is arbitrary; no turn is counted before the first move. **Constraints** 1. $ 1 \leq n, m \leq 1000 $ 2. Exactly one `'S'` and one `'T'` exist in $ G $. 3. Path must consist only of cells in $ \{ \text{'.', 'S', 'T'} \} $. 4. Number of direction changes (turns) along the path $ \leq 2 $. **Objective** Determine whether there exists a path from $ s $ to $ t $ with at most two turns. Output `"YES"` if such a path exists; otherwise output `"NO"`.
Samples
Input #1
5 5
..S..
****.
T....
****.
.....
Output #1
YES
Input #2
5 5
S....
****.
.....
.****
..T..
Output #2
NO
API Response (JSON)
{
  "problem": {
    "name": "B. Igor and his way to work",
    "description": {
      "content": "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 Bank",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF793B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 Bank...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "被闹钟吵醒后,金融分析师 Igor 急匆匆赶往工作地点。他吃完早餐,坐进车里。可惜的是,当他打开 GPS 导航时,发现他所居住的城市 Bankopolis 的一些道路因施工而封闭。此外,Igor 的方向盘有问题,因此他在前往银行的路上最多只能转弯两次。\n\nBankopolis 呈现为一个 #cf_span[n] 行 #cf_span[m] 列的网格。Igor 需要找到一条从家到银行的路径,该路径最...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid.  \nLet $ G \\in \\{ \\text{'.', 'X', 'S', 'T'} \\}^{n \\times m} $ be the grid, where:  \n- `'.'` denotes an open cell,  \n- ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments