J. Robots at Warehouse

Codeforces

IDCF10097J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Vitaly works at the warehouse. The warehouse can be represented as a grid of n × m cells, each of which either is free or is occupied by a container. From every free cell it's possible to reach every other free cell by moving only through the cells sharing a side. Besides that, there are two robots in the warehouse. The robots are located in different free cells. Vitaly wants to swap the robots. Robots can move only through free cells sharing a side, moreover, they can't be in the same cell at the same time or move through each other. Find out if the swap can be done. The first line contains two positive integers n and m (2 ≤ n·m ≤ 200000) — the sizes of the warehouse. Each of the next n lines contains m characters. The j-th character of the i-th line is «_._» if the corresponding cell is free, «_#_» if there is a container on it, «_1_» if it's occupied by the first robot, and «_2_» if it's occupied by the second robot. The characters «_1_» and «_2_» appear exactly once in these lines. Output «_YES_» (without quotes) if the robots can be swapped, and «_NO_» (without quotes) if that can't be done. ## Input The first line contains two positive integers n and m (2 ≤ n·m ≤ 200000) — the sizes of the warehouse.Each of the next n lines contains m characters. The j-th character of the i-th line is «_._» if the corresponding cell is free, «_#_» if there is a container on it, «_1_» if it's occupied by the first robot, and «_2_» if it's occupied by the second robot. The characters «_1_» and «_2_» appear exactly once in these lines. ## Output Output «_YES_» (without quotes) if the robots can be swapped, and «_NO_» (without quotes) if that can't be done. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 2 \leq n \cdot m \leq 200000 $. Let $ G = (V, E) $ be a grid graph of size $ n \times m $, where each cell $ (i,j) $ is a vertex, and edges connect horizontally/vertically adjacent free cells (i.e., cells marked `'.'`, `'1'`, or `'2'`). Let $ r_1, r_2 \in V $ be the distinct positions of the two robots (marked `'1'` and `'2'`). **Constraints** 1. Each cell is either: - Free (`'.'`), - Occupied by a container (`'#'`), - Occupied by robot 1 (`'1'`), - Occupied by robot 2 (`'2'`). 2. `'1'` and `'2'` appear exactly once. 3. All free cells (including $ r_1 $ and $ r_2 $) form a single connected component under 4-directional adjacency. **Objective** Determine whether there exists a finite sequence of valid moves such that: - Each move consists of one robot moving to an adjacent free cell. - Robots never occupy the same cell simultaneously. - Robots never pass through each other (i.e., no swap of positions in a single step). - The final configuration has robot 1 at $ r_2 $ and robot 2 at $ r_1 $. Output `YES` if such a sequence exists, `NO` otherwise.

API Response (JSON)

{
  "problem": {
    "name": "J. Robots at Warehouse",
    "description": {
      "content": "Vitaly works at the warehouse. The warehouse can be represented as a grid of n × m cells, each of which either is free or is occupied by a container. From every free cell it's possible to reach every ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vitaly works at the warehouse. The warehouse can be represented as a grid of n × m cells, each of which either is free or is occupied by a container. From every free cell it's possible to reach every ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 2 \\leq n \\cdot m \\leq 200000 $.  \nLet $ G = (V, E) $ be a grid graph of size $ n \\times m $, where each cell $ (i,j) $ is a vertex, and edges con...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments