Question
Make Rows or Columns Palindromic
You are given a binary matrix of size m × n, where each cell contains either 0 or 1.
A row is palindromic if it reads the same from left to right and right to left.
A column is palindromic if it reads the same from top to bottom and bottom to top.
You may flip any individual cell in the matrix:
-
change
0to1, or -
change
1to0.
Your task is to find the minimum number of flips required to make either:
-
every row palindromic
-
every column palindromic
Print the minimum flips needed among the two choices.
Input
- The first line contains two integers m and n, representing the number of rows and columns.
- The next m lines each contain n space-separated integers (0 or 1) describing the matrix.
Output
- Print a single integer — the minimum number of flips required to make either all rows palindromic or all columns palindromic.
Example
Example 1:
Input:
3 3
1 0 0
0 0 0
0 0 1
Output:
2
Explanation:
In the given grid, the rows are not palindromic in their current form.
By flipping two cells, each row can be made to read the same from left to right and right to left.
No single flip can achieve this for all rows or all columns.
Therefore, the minimum number of flips required is 2.
Example 2:
Input:
3 2
0 1
0 1
0 0
Output:
1
Explanation:
In the given grid, the columns are not palindromic initially.
By flipping one cell, each column reads the same from top to bottom and bottom to top.
Since this can be achieved with a single flip, the minimum number of flips required is 1.
Input:
3 3
1 0 0
0 0 0
0 0 1
Output:
2
Explanation:
In the given grid, the rows are not palindromic in their current form.
By flipping two cells, each row can be made to read the same from left to right and right to left.
No single flip can achieve this for all rows or all columns.
Therefore, the minimum number of flips required is 2.
Example 2:
Input:
3 2
0 1
0 1
0 0
Output:
1
Explanation:
In the given grid, the columns are not palindromic initially.
By flipping one cell, each column reads the same from top to bottom and bottom to top.
Since this can be achieved with a single flip, the minimum number of flips required is 1.