Guest User

Untitled

a guest
Dec 14th, 2013
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.89 KB | None | 0 0
  1. import java.util.*;
  2. import java.math.*;
  3. import static java.lang.Math.*;
  4.  
  5. public class PalindromeMatrix {
  6.    
  7.     boolean hasBit(int mask, int pos) {
  8.         return (mask & (1 << pos)) != 0;
  9.     }
  10.    
  11.     public int minChange(String[] A, int rowCount, int columnCount) {
  12.         int n = A.length, m = A[0].length();
  13.         int[] goodMasksN = new int[5000];
  14.         int cntN = 0;
  15.         int[] goodMasksM = new int[5000];
  16.         int cntM = 0;
  17.        
  18.         for (int i = 0; i < (1 << n); i++) {
  19.             if (Integer.bitCount(i) == rowCount) {
  20.                 goodMasksN[cntN++] = i;
  21.             }
  22.         }
  23.         for (int i = 0; i < (1 << m); i++) {
  24.             if (Integer.bitCount(i) == columnCount) {
  25.                 goodMasksM[cntM++] = i;
  26.             }
  27.         }
  28.        
  29.         int ans = n * m;
  30.        
  31.         int[] precalc = new int[(n / 2) * (m / 2) * 16];
  32.         for (int i = 0; i < n / 2; i++) {
  33.             for (int j = 0; j < m / 2; j++) {
  34.                 for (int it1 = 0; it1 <= 1; it1++) {
  35.                     for (int it2 = 0; it2 <= 1; it2++) {
  36.                         for (int it3 = 0; it3 <= 1; it3++) {
  37.                             for (int it4 = 0; it4 <= 1; it4++) {
  38.                                 int curans = 0;
  39.                                 boolean h1 = it1 == 1;
  40.                                 boolean h2 = it2 == 1;
  41.                                 boolean v1 = it3 == 1;
  42.                                 boolean v2 = it4 == 1;
  43.                                 char val11 = A[i].charAt(j);
  44.                                 char val12 = A[i].charAt(m - j - 1);
  45.                                 char val21 = A[n - i - 1].charAt(j);
  46.                                 char val22 = A[n - i - 1].charAt(m - j - 1);
  47.                                 if (!h1 && !h2 && !v1 && !v2) {
  48.                                    
  49.                                 } else if (h1 && !h2 && !v1 && !v2) {
  50.                                     if (val11 != val12) {
  51.                                         curans++;
  52.                                     }
  53.                                 } else if (!h1 && h2 && !v1 && !v2) {
  54.                                     if (val21 != val22) {
  55.                                         curans++;
  56.                                     }
  57.                                 } else if (!h1 && !h2 && v1 && !v2) {
  58.                                     if (val11 != val21) {
  59.                                         curans++;
  60.                                     }
  61.                                 } else if (!h1 && !h2 && !v1 && v2) {
  62.                                     if (val12 != val22) {
  63.                                         curans++;
  64.                                     }
  65.                                 } else if (h1 && h2 && !v1 && !v2) {
  66.                                     if (val11 != val12) {
  67.                                         curans++;
  68.                                     }
  69.                                     if (val21 != val22) {
  70.                                         curans++;
  71.                                     }
  72.                                 } else if (!h1 && !h2 && v1 && v2) {
  73.                                     if (val11 != val21) {
  74.                                         curans++;
  75.                                     }
  76.                                     if (val12 != val22) {
  77.                                         curans++;
  78.                                     }
  79.                                 } else if (h1 && !h2 && v1 && !v2) {
  80.                                     if (val11 != val12 || val11 != val21) {
  81.                                         curans++;
  82.                                     }
  83.                                 } else if (h1 && !h2 && !v1 && v2) {
  84.                                     if (val12 != val11 || val12 != val22) {
  85.                                         curans++;
  86.                                     }
  87.                                 } else if (!h1 && h2 && v1 && !v2) {
  88.                                     if (val21 != val22 || val21 != val11) {
  89.                                         curans++;
  90.                                     }
  91.                                 } else if (!h1 && h2 && !v1 && v2) {
  92.                                     if (val22 != val21 || val22 != val12) {
  93.                                         curans++;
  94.                                     }
  95.                                 } else {
  96.                                     int cnt1 = 0;
  97.                                     if (val11 == '1') {
  98.                                         cnt1++;
  99.                                     }
  100.                                     if (val12 == '1') {
  101.                                         cnt1++;
  102.                                     }
  103.                                     if (val21 == '1') {
  104.                                         cnt1++;
  105.                                     }
  106.                                     if (val22 == '1') {
  107.                                         cnt1++;
  108.                                     }
  109.                                     curans += min(cnt1, 4 - cnt1);
  110.                                 }
  111.                                 int pos = (i * m / 2 + j) * 16 + 1 * it1 + 2 * it2 + 4 * it3 + 8 * it4;
  112.                                 precalc[pos] = curans;
  113.                             }
  114.                         }
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.        
  120.         for (int iN = 0; iN < cntN; iN++) {
  121.             int maskN = goodMasksN[iN];
  122.             for (int iM = 0; iM < cntM; iM++) {
  123.                 int maskM = goodMasksM[iM];
  124.                 int curans = 0;
  125.                 for (int i = 0; i < n / 2; i++) {
  126.                     for (int j = 0; j < m / 2; j++) {
  127.                         boolean h1 = (maskN & (1 << i)) != 0;
  128.                         boolean h2 = (maskN & (1 << (n - i - 1))) != 0;
  129.                         boolean v1 = (maskM & (1 << j)) != 0;
  130.                         boolean v2 = (maskM & (1 << (m - j - 1))) != 0;
  131.                         int mask = 0;
  132.                         if (h1) {
  133.                             mask |= 1;
  134.                         }
  135.                         if (h2) {
  136.                             mask |= 2;
  137.                         }
  138.                         if (v1) {
  139.                             mask |= 4;
  140.                         }
  141.                         if (v2) {
  142.                             mask |= 8;
  143.                         }
  144.                         curans += precalc[(((i * m >> 1) + j) << 4) + mask];
  145.                     }
  146.                 }
  147.                 ans = min(ans, curans);
  148.             }
  149.         }
  150.        
  151.         return ans;
  152.     }
  153. }
Advertisement
Add Comment
Please, Sign In to add comment