codeforce:1720C

Posted on

# codeforces 1720C

# The problem

C. Corners
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a matrix consisting of n rows and m columns. Each cell of this matrix contains 0 or 1.
Let’s call a square of size 2×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.
Find the maximum number of operations that you can do with the given matrix.

Input
The first line contains one integer t (1≤t≤500) — the number of test cases. Then follow the descriptions of each test case.
The first line of each test case contains two integers n and m (2≤n,m≤500) — the size of the matrix.
Each of the following n lines contains a binary string of length m — the description of the matrix.
It is guaranteed that the sum of n and the sum of m over all test cases does not exceed 1000.
Output
For each test case output the maximum number of operations you can do with the given matrix.

# At first, I didn’t have a clue. So I tried to do a brute force. Didn’t work out of course.The data volume is too large. So I was wondering whether it could be solved by dynamic programing. I tried this:

sum[x][y]=max(sum[x-1][y-1]+b[x][y]-b[x-1][y-1],sum[x-2][y-2]+b[x][y]-b[x-2][y-2])

# sum[][] stands for the maximum number we need to solve, and b[x][y] stands for the sum of a[1~x][1~y].
# It seemed closed, but got a WA. Well, the initial square was harder to define then I thought. After a few tried, I decided to abandon this dp method.
# It was some time before the right answer occur to me. It’s actually pretty easy.
# Search every square of size 2*2, if exists one square contains at least two ‘0’,then the maximum number is the number of ‘1’, else the maximun number is the number of ‘1’- 1(if there contains ‘0’) or the maximun number is the number of ‘1’- 2(if the whole square is ‘1’)