TopCoder SRM600: PalindromeMatrixDiv2

N,M は 2 以上 8 以下のため、「回文になる列の集合」と「回文になる行の集合」について全探索できる。

回文になる行と列がはっきりしていると、{ A[y][x] , A[H-1-y][x] , A[y][W-1-x] , A[H-1-y][W-1-x] } について、同じ値にしないといけないペア情報が確定する。

あとはそれらのペアの連結集合について、同じ値に変換するのに必要な最小の操作数を求めれば良い。

public class PalindromeMatrixDiv2 {
    static public int BitCount(long x) {
        int bitCount = 0;
        for (; x != 0; x = x & (x - 1)) bitCount++;
        return bitCount;
    }

    public class DisjointSet {
        private int[] group;
        public DisjointSet(int n) {
            group = new int[n];
            Clear();
        }
        public bool unionSet(int x, int y) {
            x = root(x); y = root(y);
            if (x != y) {
                if (group[y] < group[x]) return unionSet(y, x);
                group[x] += group[y];
                group[y] = x;
            }
            return x != y;
        }
        public bool isSameSet(int x, int y) { return root(x) == root(y); }
        public int root(int x) { return group[x] < 0 ? x : group[x] = root(group[x]); }
        public int size(int x) { return -group[root(x)]; }
        public void Clear() {
            for (int i = 0; i < group.Length; i++) {
                group[i] = -1;
            }
        }
    };


    public int minChange(string[] A, int rowCount, int columnCount) {
        int R = A.Length;
        int C = A[0].Length;

        int ans = int.MaxValue;
        for (int rowBit = 0; rowBit < 1 << R; rowBit++) {
            if (BitCount(rowBit) != rowCount) continue;
            for (int colBit = 0; colBit < 1 << C; colBit++) {
                if (BitCount(colBit) != columnCount) continue;

                DisjointSet ds = new DisjointSet(R * C);
                Func<int, int, int> toId = (row, col) => row * C + col;
                for (int i = 0; i < R; i++) {
                    if (((1 << i) & rowBit) != 0) {
                        for (int j = 0; j < C; j++) {
                            ds.unionSet(toId(i, j), toId(i, C - 1 - j));
                        }
                    }
                }
                for (int i = 0; i < C; i++) {
                    if (((1 << i) & colBit) != 0) {
                        for (int j = 0; j < R; j++) {
                            ds.unionSet(toId(j, i), toId(R - 1 - j, i));
                        }
                    }
                }

                Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
                for (int i = 0; i < R * C; i++) {
                    int r = ds.root(i);
                    if (dic.ContainsKey(r) == false)
                        dic[r] = new List<int>();
                    dic[r].Add(i);
                }
                int change = 0;
                foreach (var d in dic) {
                    int zero = 0, one = 0;
                    foreach (var v in d.Value) {
                        int r = v / C;
                        int c = v % C;
                        if (A[r][c] == '1') one++;
                        else zero++;
                    }
                    change += Math.Min(zero, one);
                }
                ans = Math.Min(ans, change);
            }
        }
        return ans;
    }
}