#K65172. Special Matrix Transformation
Special Matrix Transformation
Special Matrix Transformation
You are given a binary matrix of size n × m. You are allowed to flip any element (i.e., change a 0 to a 1 or a 1 to a 0) any number of times. Your task is to determine whether it is possible to transform the given matrix into a special matrix.
A special matrix is defined as a matrix where:
- Every element is either 0 or 1.
- The sum of the elements in every row is equal to the sum of the elements in every column.
In mathematical terms, if every row and every column sums to a common integer k, then the total number of ones in the matrix is n × k (from rows) and also m × k (from columns). Hence, for a non-trivial solution (with k > 0), it is necessary that:
\( n \times k = m \times k \)
which in turn implies that unless k = 0 (an all-zero matrix), the matrix must be square. However, since you are allowed to flip bits arbitrarily, your task is to only check if the total number of ones can be distributed evenly among the rows and columns based on the current count of ones.
Note: The solution approach adopted here is to compute the total number of ones in the matrix and verify whether this total is divisible by both n and m. If both conditions are satisfied, output YES
; otherwise, output NO
.
inputFormat
The input is read from stdin and has the following format:
T n m row1 row2 ... rown
Where:
- T is the number of test cases.
- For each test case, the first line contains two integers n and m, representing the number of rows and columns respectively.
- The next n lines each contain m integers (either 0 or 1) separated by spaces, representing the matrix.
outputFormat
For each test case, output a single line to stdout containing either YES
if it is possible to transform the matrix into a special matrix, or NO
otherwise.
1
2 2
0 1
1 0
YES
</p>