{"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 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.\n\nVitaly 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.\n\nThe first line contains two positive integers n and m (2 ≤ n·m ≤ 200000) — the sizes of the warehouse.\n\nEach 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.\n\nOutput «_YES_» (without quotes) if the robots can be swapped, and «_NO_» (without quotes) if that can't be done.\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput «_YES_» (without quotes) if the robots can be swapped, and «_NO_» (without quotes) if that can't be done.\n\n[samples]","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 connect horizontally/vertically adjacent free cells (i.e., cells marked `'.'`, `'1'`, or `'2'`).  \nLet $ r_1, r_2 \\in V $ be the distinct positions of the two robots (marked `'1'` and `'2'`).  \n\n**Constraints**  \n1. Each cell is either:  \n   - Free (`'.'`),  \n   - Occupied by a container (`'#'`),  \n   - Occupied by robot 1 (`'1'`),  \n   - Occupied by robot 2 (`'2'`).  \n2. `'1'` and `'2'` appear exactly once.  \n3. All free cells (including $ r_1 $ and $ r_2 $) form a single connected component under 4-directional adjacency.  \n\n**Objective**  \nDetermine whether there exists a finite sequence of valid moves such that:  \n- Each move consists of one robot moving to an adjacent free cell.  \n- Robots never occupy the same cell simultaneously.  \n- Robots never pass through each other (i.e., no swap of positions in a single step).  \n- The final configuration has robot 1 at $ r_2 $ and robot 2 at $ r_1 $.  \n\nOutput `YES` if such a sequence exists, `NO` otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10097J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}