{"problem":{"name":"D. Robot in Basement","description":{"content":"The Professor has lost his home robot yet again. After some thinking Professor understood that he had left the robot in the basement. The basement in Professor's house is represented by a rectangle _","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF97D"},"statements":[{"statement_type":"Markdown","content":"The Professor has lost his home robot yet again. After some thinking Professor understood that he had left the robot in the basement.\n\nThe basement in Professor's house is represented by a rectangle _n_ × _m_, split into 1 × 1 squares. Some squares are walls which are impassable; other squares are passable. You can get from any passable square to any other passable square moving through edge-adjacent passable squares. One passable square is the exit from the basement. The robot is placed exactly in one passable square. Also the robot may be placed in the exit square.\n\nProfessor is scared of going to the dark basement looking for the robot at night. However, he has a basement plan and the robot's remote control. Using the remote, Professor can send signals to the robot to shift one square left, right, up or down. When the robot receives a signal, it moves in the required direction if the robot's neighboring square in the given direction is passable. Otherwise, the robot stays idle.\n\nProfessor wrote a sequence of _k_ commands on a piece of paper. He thinks that the sequence can lead the robot out of the basement, wherever it's initial position might be. Professor programmed another robot to press the required buttons on the remote according to the notes on the piece of paper. Professor was just about to run the program and go to bed, when he had an epiphany.\n\nExecuting each command takes some energy and Professor doesn't want to get huge electricity bill at the end of the month. That's why he wants to find in the sequence he has written out the minimal possible prefix that would guarantee to lead the robot out to the exit after the prefix is fulfilled. And that's the problem Professor challenges you with at this late hour.\n\n## Input\n\nThe first line contains three integers _n_, _m_ and _k_ (3 ≤ _n_, _m_ ≤ 150, 1 ≤ _k_ ≤ 105). Next _n_ lines contain _m_ characters each — that is the Professor's basement's description: \"_#_\" stands for a wall, \"_._\" stands for a passable square and \"_E_\" stands for the exit from the basement (this square also is passable). It is possible to get from each passable square to the exit, all squares located by the _n_ × _m_ rectangle's perimeter are the walls. Exactly one square is the exit from the basement. The last line contains _k_ characters, the description of the sequence of commands that Professor has written out on a piece of paper. \"_L_\", \"_R_\", \"_U_\", \"_D_\" stand for commands left, right, up and down correspondingly.\n\n## Output\n\nPrint in the output file the length of the smallest possible prefix that will lead the robot to the exit square. In other words, wherever the robot had been positioned initially, it should be positioned in the exit square **after all** the commands from the prefix are fulfilled (during doing commands the robot can come and leave the exit square, but only the last position of the robot is interesting for us). If Professor is mistaken and no prefix (including the whole sequence) can bring the robot to the exit, print \"-1\" (without the quotes). If there is the only passable square and it is the exit, print \"0\" (without the quotes).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"教授又一次失去了他的家用机器人。经过一番思考，教授意识到他把机器人留在了地下室。\n\n教授家的地下室是一个大小为 #cf_span[n × m] 的矩形，被划分为 #cf_span[1 × 1] 的方格。某些方格是墙壁，无法通过；其他方格是可通行的。你可以通过边相邻的可通行方格，从任意一个可通行方格到达另一个可通行方格。其中一个可通行方格是地下室的出口。机器人恰好位于一个可通行方格上，也可能位于出口方格上。\n\n教授害怕在夜间进入黑暗的地下室寻找机器人。然而，他拥有地下室的平面图和机器人的遥控器。通过遥控器，教授可以向机器人发送左、右、上、下四个方向的指令。当机器人接收到指令时，如果该方向上相邻的方格是可通行的，则机器人会向该方向移动一格；否则，机器人保持不动。\n\n教授在一张纸上写下了包含 #cf_span[k] 条指令的序列。他认为，无论机器人初始位于哪个位置，该序列都能引导机器人离开地下室。教授又编程了另一个机器人，让它根据纸上的指令序列操作遥控器。就在教授准备运行程序去睡觉时，他突然灵光一闪。\n\n执行每条指令都需要消耗能量，而教授不希望月底收到一笔巨额电费账单。因此，他希望在自己写下的序列中，找出最短的前缀，使得在执行完该前缀后，无论机器人初始位置如何，它都必定位于出口处。这就是教授在深夜向你提出的挑战。\n\n第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[3 ≤ n, m ≤ 150]，#cf_span[1 ≤ k ≤ 10^5]）。接下来 #cf_span[n] 行，每行包含 #cf_span[m] 个字符，描述教授的地下室：\"_#_\" 表示墙壁，\"_._\" 表示可通行方格，\"_E_\" 表示地下室的出口（该方格也是可通行的）。保证从每个可通行方格都能到达出口，位于 #cf_span[n × m] 矩形边界上的所有方格均为墙壁。恰好有一个出口方格。最后一行包含 #cf_span[k] 个字符，描述教授写在纸上的指令序列。\"_L_\"、\"_R_\"、\"_U_\"、\"_D_\" 分别代表左、右、上、下指令。\n\n请在输出文件中输出能保证将机器人引导至出口方格的最短前缀长度。换句话说，无论机器人初始位于何处，在执行完该前缀的所有指令后，机器人必须位于出口方格（执行过程中机器人可以进出出口，但只关心最终位置）。如果教授的设想有误，没有任何前缀（包括整个序列）能将机器人带到出口，请输出 \"-1\"（不含引号）。如果只有一个可通行方格且它就是出口，请输出 \"0\"（不含引号）。\n\n## Input\n\n第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[3 ≤ n, m ≤ 150]，#cf_span[1 ≤ k ≤ 10^5]）。接下来 #cf_span[n] 行，每行包含 #cf_span[m] 个字符，描述教授的地下室：\"_#_\" 表示墙壁，\"_._\" 表示可通行方格，\"_E_\" 表示地下室的出口（该方格也是可通行的）。保证从每个可通行方格都能到达出口，位于 #cf_span[n × m] 矩形边界上的所有方格均为墙壁。恰好有一个出口方格。最后一行包含 #cf_span[k] 个字符，描述教授写在纸上的指令序列。\"_L_\"、\"_R_\"、\"_U_\"、\"_D_\" 分别代表左、右、上、下指令。\n\n## Output\n\n请在输出文件中输出能保证将机器人引导至出口方格的最短前缀长度。换句话说，无论机器人初始位于何处，在执行完该前缀的所有指令后，机器人必须位于出口方格（执行过程中机器人可以进出出口，但只关心最终位置）。如果教授的设想有误，没有任何前缀（包括整个序列）能将机器人带到出口，请输出 \"-1\"（不含引号）。如果只有一个可通行方格且它就是出口，请输出 \"0\"（不含引号）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the dimensions of the grid, and $ k \\in \\mathbb{Z} $ the length of the command sequence.  \nLet $ G = (V, E) $ be a grid graph of size $ n \\times m $, where:  \n- Each cell $ (i, j) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ is a vertex.  \n- $ V_{\\text{pass}} \\subseteq V $: set of passable cells (denoted by '.').  \n- $ v_{\\text{exit}} \\in V_{\\text{pass}} $: unique exit cell (denoted by 'E').  \n- $ V_{\\text{wall}} = V \\setminus V_{\\text{pass}} $: wall cells (denoted by '#').  \n- Edges exist between edge-adjacent (up/down/left/right) passable cells.  \n\nLet $ C = c_1 c_2 \\dots c_k $ be a sequence of commands, where each $ c_i \\in \\{ \\text{L}, \\text{R}, \\text{U}, \\text{D} \\} $.  \nFor a command $ c $ and position $ (x, y) $, define the move function:  \n- $ \\text{move}((x, y), \\text{L}) = (x, y-1) $ if $ (x, y-1) \\in V_{\\text{pass}} $, else $ (x, y) $.  \n- Similarly for R, U, D.  \n\nLet $ S_t \\subseteq V_{\\text{pass}} $ denote the set of possible robot positions after executing the first $ t $ commands, starting from *any* initial passable position.  \nInitialize $ S_0 = V_{\\text{pass}} $.  \nFor $ t = 1 $ to $ k $:  \n$ S_t = \\{ \\text{move}(p, c_t) \\mid p \\in S_{t-1} \\} $\n\n**Constraints**  \n1. $ 3 \\leq n, m \\leq 150 $  \n2. $ 1 \\leq k \\leq 10^5 $  \n3. Exactly one exit cell $ v_{\\text{exit}} $.  \n4. All perimeter cells are walls.  \n5. The graph induced by $ V_{\\text{pass}} $ is connected.  \n\n**Objective**  \nFind the smallest $ t \\in \\{0, 1, \\dots, k\\} $ such that $ S_t = \\{ v_{\\text{exit}} \\} $.  \nIf no such $ t $ exists, output $ -1 $.  \nIf $ |V_{\\text{pass}}| = 1 $ and $ V_{\\text{pass}} = \\{ v_{\\text{exit}} \\} $, output $ 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF97D","tags":["bitmasks","brute force","implementation"],"sample_group":[["5 5 7\n#####\n#...#\n#...#\n#E..#\n#####\nUULLDDR","6"],["5 5 7\n#####\n#.#.#\n#...#\n#E..#\n#####\nUULLDDR","\\-1"],["5 3 2\n###\n#.#\n#.#\n#E#\n###\nDD","2"]],"created_at":"2026-03-03 11:00:39"}}