Swapping in a matrix
All submissions for this problem are available.
You are given a binary matrix (i.e. each element of matrix is either 0 or 1) of size n × n. You want to re-arrange 1's in such a way that they form a rectangular region. Note that the rectangular region should be made of only 1's, and all the 1's of the entire matrix should be in this rectangular region.
For achieving rectangular region, you can swap any two elements of the matrix. Please find out the minimum number of swaps needed. If it is not possible to re-arrange 1's in the desired way, please print -1.
- First line of the input contains a single integer T denoting number of test cases.
- Description of T test cases follows.
- First line of each test case will contain a single integer n denoting dimension of matrix.
- Each of next n lines will contain n space separated integers denoting the ith row of the matrix.
- For each test case, print a single line containing a single integer denoting minimum number of swaps needed or -1 depending on the situation.
- 1 ≤ T ≤ 2
- 1 ≤ n ≤ 1000
- Each entry of the matrix will either be 0 or 1
Input: 2 1 0 1 1 Output: 0 0
Example case 1. There is no 1 in the array. So no swap is required. Hence answer is 0.
Example case 2. There is exactly one 1. It already forms a rectangular region of dimension 1 × 1. So here also, no swap is required. Hence answer is 0.
Input: 2 2 0 1 1 0 2 1 1 1 0 Output: 1 -1
Example case 1. You can swap 1 of second row first column with 0 of first row first column.
After the swap, matrix will look as follows.
1 1 0 0
Here all the 1's form a rectangular region of dimension 1 × 2. In this case, 1 swap will be needed.
Note that you can also swap 1 at first row second column with 0 at second row second column too.
Matrix after this swap will be following.
0 0 1 1
So you need 1 swap in this case too.
So overall, you need 1 swap.
Example case 2. There is no way to create a rectangular region containing 3 1's in a matrix of dimension 2 × 2, hence answer is -1.
Large IO Warning
Input in the problem is huge. Please use faster input output methods. Use scanf/printf instead of cin/cout.
|Tags||2d, admin2, easy, factorization, hump2015, prefix-sum|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.