{"problem":{"name":"C. Cycle In Maze","description":{"content":"The Robot is in a rectangular maze of size _n_ × _m_. Each cell of the maze is either empty or occupied by an obstacle. The Robot can move between neighboring cells on the side left (the symbol \"_L_\")","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":15000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF769C"},"statements":[{"statement_type":"Markdown","content":"The Robot is in a rectangular maze of size _n_ × _m_. Each cell of the maze is either empty or occupied by an obstacle. The Robot can move between neighboring cells on the side left (the symbol \"_L_\"), right (the symbol \"_R_\"), up (the symbol \"_U_\") or down (the symbol \"_D_\"). The Robot can move to the cell only if it is empty. Initially, the Robot is in the empty cell.\n\nYour task is to find **lexicographically minimal** Robot's cycle with length **exactly** _k_, which begins and ends in the cell where the Robot was initially. It is allowed to the Robot to visit any cell many times (including starting).\n\nConsider that Robot's way is given as a line which consists of symbols \"_L_\", \"_R_\", \"_U_\" and \"_D_\". For example, if firstly the Robot goes down, then left, then right and up, it means that his way is written as \"_DLRU_\".\n\nIn this task you **don't need** to minimize the length of the way. Find the minimum lexicographical (in alphabet order as in the dictionary) line which satisfies requirements above.\n\n## Input\n\nThe first line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _m_ ≤ 1000, 1 ≤ _k_ ≤ 106) — the size of the maze and the length of the cycle.\n\nEach of the following _n_ lines contains _m_ symbols — the description of the maze. If the symbol equals to \"_._\" the current cell is empty. If the symbol equals to \"_*_\" the current cell is occupied by an obstacle. If the symbol equals to \"_X_\" then initially the Robot is in this cell and it is empty. It is guaranteed that the symbol \"_X_\" is found in the maze exactly once.\n\n## Output\n\nPrint the lexicographically minimum Robot's way with the length exactly _k_, which starts and ends in the cell where initially Robot is. If there is no such way, print \"_IMPOSSIBLE_\"(without quotes).\n\n[samples]\n\n## Note\n\nIn the first sample two cyclic ways for the Robot with the length 2 exist — \"_UD_\" and \"_RL_\". The second cycle is lexicographically less.\n\nIn the second sample the Robot should move in the following way: down, left, down, down, left, left, left, right, right, right, up, up, right, up.\n\nIn the third sample the Robot can't move to the neighboring cells, because they are occupied by obstacles.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"机器人位于一个大小为 $n × m$ 的矩形迷宫中。迷宫的每个格子要么为空，要么被障碍物占据。机器人可以在相邻的格子之间移动，方向为左（符号 \"_L_\"）、右（符号 \"_R_\"）、上（符号 \"_U_\"）或下（符号 \"_D_\"）。机器人只能移动到空的格子。初始时，机器人位于一个空格子中。\n\n你的任务是找到一条*字典序最小*的机器人回路，其长度*恰好*为 $k$，且起点和终点均为机器人初始所在的格子。允许机器人多次访问任意格子（包括起始格子）。\n\n机器人的路径用由符号 \"_L_\"、\"_R_\"、\"_U_\" 和 \"_D_\" 组成的字符串表示。例如，若机器人先向下，再向左，然后向右，最后向上，则其路径表示为 \"_DLRU_\"。\n\n在本题中，你*不需要*最小化路径长度。请找出满足上述要求的字典序最小（按字母顺序，如同字典排序）的字符串。\n\n第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 1000$，$1 ≤ k ≤ 10^6$）——迷宫的大小和回路的长度。\n\n接下来的 $n$ 行，每行包含 $m$ 个字符——描述迷宫。若字符为 \"_._\"，表示当前格子为空；若为 \"_*_\"，表示当前格子被障碍物占据；若为 \"_X_\"，则表示机器人初始位于该格子，且该格子为空。保证字符 \"_X_\" 在迷宫中恰好出现一次。\n\n请输出一条长度恰好为 $k$、起点和终点均为机器人初始位置的字典序最小的机器人路径。如果不存在这样的路径，请输出 \"_IMPOSSIBLE_\"（不含引号）。\n\n在第一个样例中，存在两条长度为 $2$ 的回路：\"_UD_\" 和 \"_RL_\"。其中后者字典序更小。\n\n在第二个样例中，机器人应按如下方式移动：下、左、下、下、左、左、左、右、右、右、上、上、右、上。\n\n在第三个样例中，机器人无法移动到任何相邻格子，因为它们都被障碍物占据。\n\n## Input\n\n第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 1000$，$1 ≤ k ≤ 10^6$）——迷宫的大小和回路的长度。接下来的 $n$ 行，每行包含 $m$ 个字符——描述迷宫。若字符为 \"_._\"，表示当前格子为空；若为 \"_*_\"，表示当前格子被障碍物占据；若为 \"_X_\"，则表示机器人初始位于该格子，且该格子为空。保证字符 \"_X_\" 在迷宫中恰好出现一次。\n\n## Output\n\n请输出一条长度恰好为 $k$、起点和终点均为机器人初始位置的字典序最小的机器人路径。如果不存在这样的路径，请输出 \"_IMPOSSIBLE_\"（不含引号）。\n\n[samples]\n\n## Note\n\n在第一个样例中，存在两条长度为 $2$ 的回路：\"_UD_\" 和 \"_RL_\"。其中后者字典序更小。在第二个样例中，机器人应按如下方式移动：下、左、下、下、左、左、左、右、右、右、上、上、右、上。在第三个样例中，机器人无法移动到任何相邻格子，因为它们都被障碍物占据。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ denote the dimensions of the maze and the required cycle length.  \nLet $ G = (V, E) $ be a grid graph where:  \n- $ V = \\{ (i, j) \\mid 1 \\le i \\le n, 1 \\le j \\le m \\} $,  \n- $ (i, j) \\in V $ is *valid* if the cell is not an obstacle (i.e., not `*`),  \n- An edge exists between $ (i, j) $ and $ (i', j') $ iff they are adjacent (share a side) and both are valid.  \n\nLet $ s = (s_i, s_j) \\in V $ be the unique starting position marked by `X`.  \n\nLet $ \\Sigma = \\{ \\text{L}, \\text{R}, \\text{U}, \\text{D} \\} $ be the alphabet of moves, ordered lexicographically: $ \\text{D} < \\text{L} < \\text{R} < \\text{U} $.  \n\nA *walk* of length $ k $ is a sequence $ w = (m_1, m_2, \\dots, m_k) \\in \\Sigma^k $, inducing a path $ p_0, p_1, \\dots, p_k $ with $ p_0 = s $, and $ p_{\\ell} = \\text{move}(p_{\\ell-1}, m_\\ell) $ for $ \\ell = 1, \\dots, k $, such that all $ p_\\ell \\in V $.  \n\nA *cycle* is a walk with $ p_k = s $.  \n\n**Constraints**  \n1. $ 1 \\le n, m \\le 1000 $  \n2. $ 1 \\le k \\le 10^6 $  \n3. Exactly one cell contains `X` (the start $ s $)  \n4. Each cell is either `.` (empty), `*` (obstacle), or `X` (start, also empty)  \n5. All moves must stay within bounds and avoid obstacles  \n\n**Objective**  \nFind the lexicographically minimal string $ w \\in \\Sigma^k $ such that:  \n- The walk induced by $ w $ starts at $ s $,  \n- The walk ends at $ s $,  \n- All intermediate positions are valid (no obstacles or out-of-bounds).  \n\nIf no such walk exists, output `IMPOSSIBLE`.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF769C","tags":["dfs and similar","graphs","greedy","shortest paths"],"sample_group":[["2 3 2\n.**\nX..","RL"],["5 6 14\n..***.\n*...X.\n..*...\n..*.**\n....*.","DLDDLLLRRRUURU"],["3 3 4\n***\n*X*\n***","IMPOSSIBLE"]],"created_at":"2026-03-03 11:00:39"}}