codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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}$