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.