天下一プログラマーコンテスト2015予選A C: 天下一美術館
解法
http://tenka1.klab.jp/2015/explain/quala_c.htmltenka1.klab.jp
隣り合った2マスが両方Bと違い、かつ、入れ替えればBと一致する場合、それらを1つずつ変えるより入れ替えた方が少ないコストで済む。
これは「二部グラフの最大マッチング問題」に帰結することができ、これは最大フロー問題として解くことができる。
http://dopal.cs.uec.ac.jp/okamotoy/lect/2012/graphtheory/lect12.pdf
コード
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { private final int[] DX = { 0, 0, 1, -1 }; private final int[] DY = { 1, -1, 0, 0 }; public void solve() { Scanner scanner = new Scanner(System.in); int M = scanner.nextInt(); int N = scanner.nextInt(); int[][] A = new int[M][N]; int[][] B = new int[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { A[i][j] = scanner.nextInt(); } } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { B[i][j] = scanner.nextInt(); } } scanner.close(); // AとBで違う色のマスの数をカウントしておく int cnt = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (A[i][j] != B[i][j]) { cnt++; } } } // 各マスを1つの頂点として、スタートとゴールを入れたM*N+2頂点のグラフを作る int V = M * N; int source = V; int sink = V + 1; MaximumFlow graph = new MaximumFlow(V + 2, source, sink); for (int m = 0; m < M; m++) { for (int n = 0; n < N; n++) { if (A[m][n] == B[m][n]) { continue; } // 入ってくるマスと出ていくマスが市松模様になるように設定する int from = m * N + n; if (m % 2 != n % 2) { graph.addEdge(from, sink, 1); continue; } graph.addEdge(source, from, 1); // Aの中の隣り合っているマスが両方ともBと違い、かつ、入れ替えた時に両方ともBに一致する時 for (int d = 0; d < 4; d++) { int mm = m + DX[d]; int nn = n + DY[d]; if (mm < 0 || nn < 0 || mm >= M || nn >= N) { continue; } int to = mm * N + nn; if (A[mm][nn] != B[mm][nn] && A[m][n] != A[mm][nn]) { graph.addEdge(from, to, 1); } } } } // 最大マッチング int match = graph.fordFulkerson(); // match*2個のマスがコストmatchによってBに一致したので、1つづ使えるよりmatchだけ減る System.out.println(cnt - match); } public static void main(String[] args) { new Main().solve(); } } // 最大フロー問題のライブラリ class MaximumFlow { public static final int INF = 100000000; int V;// 頂点数 int source; int sink; ArrayList<Edge>[] graph; boolean[] used; @SuppressWarnings("unchecked") public MaximumFlow(int V, int source, int sink) { this.V = V; this.source = source; this.sink = sink; graph = new ArrayList[V]; for (int i = 0; i < V; i++) { graph[i] = new ArrayList<Edge>(); } used = new boolean[V]; } public void addEdge(int from, int to, int cap) { graph[from].add(new Edge(to, cap, graph[to].size())); graph[to].add(new Edge(from, 0, graph[from].size() - 1)); } public int fordFulkerson() { int flow = 0; while (true) { Arrays.fill(used, false); int f = dfsFF(source, sink, INF); if (f == 0) { break; } flow += f; } return flow; } private int dfsFF(int from, int to, int flow) { if (from == to) { return flow; } used[from] = true; for (Edge edge : graph[from]) { if (used[edge.to] || edge.cap <= 0) { continue; } int d = dfsFF(edge.to, to, Math.min(flow, edge.cap)); if (d > 0) { edge.cap -= d; graph[edge.to].get(edge.rev).cap += d; return d; } } return 0; } } class Edge { int to; int cap; int rev; public Edge(int to, int cap, int rev) { this.to = to; this.cap = cap; this.rev = rev; } }