{"problem":{"name":"E. Two Labyrinths","description":{"content":"A labyrinth is the rectangular grid, each of the cells of which is either free or wall, and it's possible to move only between free cells sharing a side. Constantine and Mike are the world leaders of","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10018E"},"statements":[{"statement_type":"Markdown","content":"A labyrinth is the rectangular grid, each of the cells of which is either free or wall, and it's possible to move only between free cells sharing a side.\n\nConstantine and Mike are the world leaders of composing the labyrinths. Each of them has just composed one labyrinth of size n × m, and now they are blaming each other for the plagiarism. They consider that the plagiarism takes place if there exists such a path from the upper-left cell to the lower-right cell that is the shortest for both labyrinths. Resolve their conflict and say if the plagiarism took place.\n\nIn the first line two integers n and m (1 ≤ n, m ≤ 500) are written — the height and the width of the labyrinths.\n\nIn the next n lines the labyrinth composed by Constantine is written. Each of these n lines consists of m characters. Each character is equal either to «_#_», which denotes a wall, or to «_._», which denotes a free cell.\n\nThe next line is empty, and in the next n lines the labyrinth composed by Mike is written in the same format. It is guaranteed that the upper-left and the lower-right cells of both labyrinths are free.\n\nOutput «_YES_» if there exists such a path from the upper-left to the lower-right cell that is the shortest for both labyrinths. Otherwise output «_NO_».\n\n## Input\n\nIn the first line two integers n and m (1 ≤ n, m ≤ 500) are written — the height and the width of the labyrinths.In the next n lines the labyrinth composed by Constantine is written. Each of these n lines consists of m characters. Each character is equal either to «_#_», which denotes a wall, or to «_._», which denotes a free cell.The next line is empty, and in the next n lines the labyrinth composed by Mike is written in the same format. It is guaranteed that the upper-left and the lower-right cells of both labyrinths are free.\n\n## Output\n\nOutput «_YES_» if there exists such a path from the upper-left to the lower-right cell that is the shortest for both labyrinths. Otherwise output «_NO_».\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 1 \\leq n, m \\leq 500 $.  \nLet $ C = (c_{i,j})_{1 \\leq i \\leq n, 1 \\leq j \\leq m} \\in \\{ \\text{`.`}, \\text{`#'} \\}^{n \\times m} $ be Constantine’s labyrinth.  \nLet $ M = (m_{i,j})_{1 \\leq i \\leq n, 1 \\leq j \\leq m} \\in \\{ \\text{`.`}, \\text{`#'} \\}^{n \\times m} $ be Mike’s labyrinth.  \nAssume $ c_{1,1} = c_{n,m} = \\text{`.`} $ and $ m_{1,1} = m_{n,m} = \\text{`.`} $.\n\nLet $ G_C = (V_C, E_C) $ be the grid graph of Constantine’s labyrinth:  \n- $ V_C = \\{ (i,j) \\mid c_{i,j} = \\text{`.`} \\} $,  \n- $ E_C = \\{ ((i,j), (i',j')) \\mid |i - i'| + |j - j'| = 1 \\} $.  \n\nLet $ G_M = (V_M, E_M) $ be the grid graph of Mike’s labyrinth, defined analogously.\n\nLet $ d_C(u,v) $ denote the shortest path distance between nodes $ u, v \\in V_C $ in $ G_C $, and $ d_M(u,v) $ analogously in $ G_M $.\n\nLet $ s = (1,1) $, $ t = (n,m) $.\n\n**Constraints**  \n1. $ s, t \\in V_C \\cap V_M $.  \n2. Both $ G_C $ and $ G_M $ are connected graphs with $ s, t \\in V_C $ and $ s, t \\in V_M $.\n\n**Objective**  \nDetermine whether:  \n$$\n\\exists \\, P \\text{ (path from } s \\text{ to } t \\text{)} \\quad \\text{such that} \\quad |P| = d_C(s,t) = d_M(s,t)\n$$  \nwhere $ |P| $ is the number of edges in path $ P $, and $ P $ is valid in both labyrinths (i.e., all cells of $ P $ are free in both $ C $ and $ M $).\n\nEquivalently:  \nIs the set of shortest paths from $ s $ to $ t $ in $ G_C $ intersecting the set of shortest paths from $ s $ to $ t $ in $ G_M $, under the constraint that all cells along the path are free in both labyrinths?\n\nOutput \"YES\" if such a path exists, \"NO\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10018E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}