2090B.md (3663B)
1 Source: https://codeforces.com/problemset/problem/2090/B 2 3 B. Pushing Balls 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Ecrade has an $n \times m$ grid, originally empty, and he has pushed several (possibly, zero) balls in it. 22 23 Each time, he can push one ball into the grid either from the leftmost edge of a particular row or the topmost edge of a particular column of the grid. 24 25 When a ball moves towards a position: 26 27 * If there is no ball originally at that position, the incoming ball will stop and occupy the position. 28 * If there is already a ball at that position, the incoming ball will stop and occupy the position, while the original ball will continue moving to the next position in the same direction. 29 30 Note that if a row or column is full (i.e., all positions in that row or column have balls), he cannot push a ball into that row or column. 31 32 Given the final state of whether there is a ball at each position of the grid, you need to determine whether it is possible for Ecrade to push the balls to reach the final state. 33 34 Input 35 36 The first line contains an integer $t$ ($1 \le t \le 10\,000$) — the number of test cases. The description of the test cases follows. 37 38 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 50$). 39 40 This is followed by $n$ lines, each containing exactly $m$ characters and consisting only of $0$ and $1$, describing the final state of the grid. There is a ball at one position of the grid if and only if the corresponding position of the given input is $1$. 41 42 It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10\,000$. 43 44 Output 45 46 For each test case, output "Yes" (without quotes) if it is possible for Ecrade to push the balls to reach the final state, and "No" (without quotes) otherwise. 47 48 You can output "Yes" and "No" in any case (for example, strings "YES", "yEs" and "yes" will be recognized as a positive response). 49 50 Example 51 52 Input 53 54 ``` 55 5 56 57 3 3 58 59 001 60 61 001 62 63 110 64 65 3 3 66 67 010 68 69 111 70 71 010 72 73 3 3 74 75 111 76 77 111 78 79 111 80 81 3 3 82 83 000 84 85 000 86 87 000 88 89 3 3 90 91 000 92 93 000 94 95 001 96 ``` 97 98 Output 99 100 ``` 101 YES 102 YES 103 YES 104 YES 105 NO 106 ``` 107 108 Note 109 110 For simplicity, if Ecrade pushes a ball from the leftmost edge of the $i$-th row, we call the operation $\text{ROW}\ i$; if he pushes a ball from the topmost edge of the $i$-th column, we call the operation $\text{COL}\ i$. 111 112 For intuitive understanding, a non-zero number $x$ in the matrix given below represents the $x$-th ball that is pushed in. 113 114 In the first test case, a possible series of operations: 115 116 $\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 3}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}0&0&0\\0&0&0\\2&1&0\end{pmatrix}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3} \begin{pmatrix}0&0&4\\0&0&3\\2&1&0\end{pmatrix}$ 117 118 In the second test case, a possible series of operations: 119 120 $\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 2} \begin{pmatrix}0&0&0\\3&2&1\\0&0&0\end{pmatrix}\xrightarrow{\text{COL}\ 2}\xrightarrow{\text{COL}\ 2} \begin{pmatrix}0&5&0\\3&4&1\\0&2&0\end{pmatrix}$ 121 122 In the third test case, a possible series of operations: 123 124 $\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 1}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}1&0&0\\2&0&0\\3&0&0\end{pmatrix}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3} \begin{pmatrix}1&0&6\\2&0&5\\3&0&4\end{pmatrix}\xrightarrow{\text{ROW}\ 1}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}7&1&6\\8&2&5\\9&3&4\end{pmatrix}$