2034C.md (2692B)
1 Source: https://codeforces.com/problemset/problem/2034/C 2 3 C. Trapped in the Witch's Labyrinth 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 In the [fourth labor of Rostam](https://www.gathertales.com/story/the-tale-of-the-haft-khan-seven-labors-of-rostam/sid-604), the legendary hero from the [Shahnameh](https://en.wikipedia.org/wiki/Shahnameh), an old witch has created a magical maze to trap him. The maze is a rectangular grid consisting of $n$ rows and $m$ columns. Each cell in the maze points in a specific direction: up, down, left, or right. The witch has enchanted Rostam so that whenever he is in a cell, he will move to the next cell in the direction indicated by that cell. 22 23  24 25 If Rostam eventually exits the maze, he will be freed from the witch's enchantment and will defeat her. However, if he remains trapped within the maze forever, he will never escape. 26 27 The witch has not yet determined the directions for all the cells. She wants to assign directions to the unspecified cells in such a way that the number of starting cells from which Rostam will be trapped forever is maximized. Your task is to find the maximum number of starting cells which make Rostam trapped. 28 29 Input 30 31 The first line of the input contains an integer $t$ ($1 \leq t \leq 10^4$), the number of test cases. 32 33 For each test case: 34 35 * The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 1000$), representing the number of rows and columns in the maze. 36 * Each of the next $n$ lines contains a string of $m$ characters representing the directions in the maze. Each character is one of the following: 37 + U (up) 38 + D (down) 39 + L (left) 40 + R (right) 41 + ? (unspecified direction) 42 43 It's guaranteed that the sum of $n \cdot m$ over all test cases is at most $10^6$. 44 45 Output 46 47 For each test case, print a single integer, the maximum number of starting cells from which Rostam will be trapped forever after assigning directions to the unspecified cells optimally. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 3 3 57 58 UUU 59 60 L?R 61 62 DDD 63 64 2 3 65 66 ??? 67 68 ??? 69 70 3 3 71 72 ?U? 73 74 R?L 75 76 RDL 77 ``` 78 79 Output 80 81 ``` 82 0 83 6 84 5 85 ``` 86 87 Note 88 89 In the first test case, all of the cells will be good no matter what you do. 90 91 In the second test case, if you assign the ?s like the picture below, all of the cells will be bad: 92 93  94 95 In the third test case, if you assign the ?s like the picture below, you will have $5$ bad cells (red-shaded cells): 96 97 