codeforces-scrape

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

1720C.md (3060B)


      1 Source: https://codeforces.com/problemset/problem/1720/C
      2 
      3 C. Corners
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a matrix consisting of $n$ rows and $m$ columns. Each cell of this matrix contains $0$ or $1$.
     22 
     23 Let's call a square of size $2 \times 2$ without one corner cell an L-shape figure. In one operation you can take one L-shape figure, with at least one cell containing $1$ and replace all numbers in it with zeroes.
     24 
     25 Find the maximum number of operations that you can do with the given matrix.
     26 
     27 Input
     28 
     29 The first line contains one integer $t$ ($1 \leq t \leq 500$) — the number of test cases. Then follow the descriptions of each test case.
     30 
     31 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 500$) — the size of the matrix.
     32 
     33 Each of the following $n$ lines contains a binary string of length $m$ — the description of the matrix.
     34 
     35 It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $1000$.
     36 
     37 Output
     38 
     39 For each test case output the maximum number of operations you can do with the given matrix.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 4 3
     49 
     50 101
     51 
     52 111
     53 
     54 011
     55 
     56 110
     57 
     58 3 4
     59 
     60 1110
     61 
     62 0111
     63 
     64 0111
     65 
     66 2 2
     67 
     68 00
     69 
     70 00
     71 
     72 2 2
     73 
     74 11
     75 
     76 11
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 8
     83 9
     84 0
     85 2
     86 ```
     87 
     88 Note
     89 
     90 In the first testcase one of the optimal sequences of operations is the following (bold font shows l-shape figure on which operation was performed):
     91 
     92 * Matrix before any operation was performed: 
     93 
     94   |  |  |  |
     95   | --- | --- | --- |
     96   | 1 | 0 | 1 |
     97   | 1 | 1 | 1 |
     98   | 0 | 1 | 1 |
     99   | 1 | 1 | 0 |
    100 * Matrix after $1$ operation was performed: 
    101 
    102   |  |  |  |
    103   | --- | --- | --- |
    104   | 1 | 0 | 0 |
    105   | 1 | 0 | 1 |
    106   | 0 | 1 | 1 |
    107   | 1 | 1 | 0 |
    108 * Matrix after $2$ operations were performed: 
    109 
    110   |  |  |  |
    111   | --- | --- | --- |
    112   | 1 | 0 | 0 |
    113   | 1 | 0 | 0 |
    114   | 0 | 1 | 1 |
    115   | 1 | 1 | 0 |
    116 * Matrix after $3$ operations were performed: 
    117 
    118   |  |  |  |
    119   | --- | --- | --- |
    120   | 1 | 0 | 0 |
    121   | 1 | 0 | 0 |
    122   | 0 | 1 | 0 |
    123   | 1 | 1 | 0 |
    124 * Matrix after $4$ operations were performed: 
    125 
    126   |  |  |  |
    127   | --- | --- | --- |
    128   | 1 | 0 | 0 |
    129   | 0 | 0 | 0 |
    130   | 0 | 1 | 0 |
    131   | 1 | 1 | 0 |
    132 * Matrix after $5$ operations were performed: 
    133 
    134   |  |  |  |
    135   | --- | --- | --- |
    136   | 1 | 0 | 0 |
    137   | 0 | 0 | 0 |
    138   | 0 | 1 | 0 |
    139   | 1 | 0 | 0 |
    140 * Matrix after $6$ operations were performed: 
    141 
    142   |  |  |  |
    143   | --- | --- | --- |
    144   | 1 | 0 | 0 |
    145   | 0 | 0 | 0 |
    146   | 0 | 0 | 0 |
    147   | 1 | 0 | 0 |
    148 * Matrix after $7$ operations were performed: 
    149 
    150   |  |  |  |
    151   | --- | --- | --- |
    152   | 0 | 0 | 0 |
    153   | 0 | 0 | 0 |
    154   | 0 | 0 | 0 |
    155   | 1 | 0 | 0 |
    156 * Matrix after $8$ operations were performed: 
    157 
    158   |  |  |  |
    159   | --- | --- | --- |
    160   | 0 | 0 | 0 |
    161   | 0 | 0 | 0 |
    162   | 0 | 0 | 0 |
    163   | 0 | 0 | 0 |
    164 
    165 In the third testcase from the sample we can not perform any operation because the matrix doesn't contain any ones.
    166 
    167 In the fourth testcase it does not matter which L-shape figure we pick in our first operation. We will always be left with single one. So we will perform $2$ operations.