Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.math.*;
- import static java.lang.Math.*;
- public class PalindromeMatrix {
- boolean hasBit(int mask, int pos) {
- return (mask & (1 << pos)) != 0;
- }
- public int minChange(String[] A, int rowCount, int columnCount) {
- int n = A.length, m = A[0].length();
- int[] goodMasksN = new int[5000];
- int cntN = 0;
- int[] goodMasksM = new int[5000];
- int cntM = 0;
- for (int i = 0; i < (1 << n); i++) {
- if (Integer.bitCount(i) == rowCount) {
- goodMasksN[cntN++] = i;
- }
- }
- for (int i = 0; i < (1 << m); i++) {
- if (Integer.bitCount(i) == columnCount) {
- goodMasksM[cntM++] = i;
- }
- }
- int ans = n * m;
- int[] precalc = new int[(n / 2) * (m / 2) * 16];
- for (int i = 0; i < n / 2; i++) {
- for (int j = 0; j < m / 2; j++) {
- for (int it1 = 0; it1 <= 1; it1++) {
- for (int it2 = 0; it2 <= 1; it2++) {
- for (int it3 = 0; it3 <= 1; it3++) {
- for (int it4 = 0; it4 <= 1; it4++) {
- int curans = 0;
- boolean h1 = it1 == 1;
- boolean h2 = it2 == 1;
- boolean v1 = it3 == 1;
- boolean v2 = it4 == 1;
- char val11 = A[i].charAt(j);
- char val12 = A[i].charAt(m - j - 1);
- char val21 = A[n - i - 1].charAt(j);
- char val22 = A[n - i - 1].charAt(m - j - 1);
- if (!h1 && !h2 && !v1 && !v2) {
- } else if (h1 && !h2 && !v1 && !v2) {
- if (val11 != val12) {
- curans++;
- }
- } else if (!h1 && h2 && !v1 && !v2) {
- if (val21 != val22) {
- curans++;
- }
- } else if (!h1 && !h2 && v1 && !v2) {
- if (val11 != val21) {
- curans++;
- }
- } else if (!h1 && !h2 && !v1 && v2) {
- if (val12 != val22) {
- curans++;
- }
- } else if (h1 && h2 && !v1 && !v2) {
- if (val11 != val12) {
- curans++;
- }
- if (val21 != val22) {
- curans++;
- }
- } else if (!h1 && !h2 && v1 && v2) {
- if (val11 != val21) {
- curans++;
- }
- if (val12 != val22) {
- curans++;
- }
- } else if (h1 && !h2 && v1 && !v2) {
- if (val11 != val12 || val11 != val21) {
- curans++;
- }
- } else if (h1 && !h2 && !v1 && v2) {
- if (val12 != val11 || val12 != val22) {
- curans++;
- }
- } else if (!h1 && h2 && v1 && !v2) {
- if (val21 != val22 || val21 != val11) {
- curans++;
- }
- } else if (!h1 && h2 && !v1 && v2) {
- if (val22 != val21 || val22 != val12) {
- curans++;
- }
- } else {
- int cnt1 = 0;
- if (val11 == '1') {
- cnt1++;
- }
- if (val12 == '1') {
- cnt1++;
- }
- if (val21 == '1') {
- cnt1++;
- }
- if (val22 == '1') {
- cnt1++;
- }
- curans += min(cnt1, 4 - cnt1);
- }
- int pos = (i * m / 2 + j) * 16 + 1 * it1 + 2 * it2 + 4 * it3 + 8 * it4;
- precalc[pos] = curans;
- }
- }
- }
- }
- }
- }
- for (int iN = 0; iN < cntN; iN++) {
- int maskN = goodMasksN[iN];
- for (int iM = 0; iM < cntM; iM++) {
- int maskM = goodMasksM[iM];
- int curans = 0;
- for (int i = 0; i < n / 2; i++) {
- for (int j = 0; j < m / 2; j++) {
- boolean h1 = (maskN & (1 << i)) != 0;
- boolean h2 = (maskN & (1 << (n - i - 1))) != 0;
- boolean v1 = (maskM & (1 << j)) != 0;
- boolean v2 = (maskM & (1 << (m - j - 1))) != 0;
- int mask = 0;
- if (h1) {
- mask |= 1;
- }
- if (h2) {
- mask |= 2;
- }
- if (v1) {
- mask |= 4;
- }
- if (v2) {
- mask |= 8;
- }
- curans += precalc[(((i * m >> 1) + j) << 4) + mask];
- }
- }
- ans = min(ans, curans);
- }
- }
- return ans;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment