#116686 (Java21) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	Grenache
提出日時	2016-09-11 20:16:52
言語	Java21 (openjdk 21)
結果	AC
実行時間	133 ms / 2,000 ms
コード長	7,345 bytes
コンパイル時間	4,010 ms
コンパイル使用メモリ	80,560 KB
実行使用メモリ	59,324 KB
最終ジャッジ日時	2023-10-24 14:49:10
合計ジャッジ時間	10,226 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	51 ms 53,740 KB
testcase_01	AC	102 ms 55,708 KB
testcase_02	AC	60 ms 51,768 KB
testcase_03	AC	53 ms 53,736 KB
testcase_04	AC	57 ms 53,804 KB
testcase_05	AC	62 ms 53,800 KB
testcase_06	AC	54 ms 53,744 KB
testcase_07	AC	97 ms 55,420 KB
testcase_08	AC	66 ms 54,380 KB
testcase_09	AC	57 ms 53,736 KB
testcase_10	AC	56 ms 51,716 KB
testcase_11	AC	98 ms 55,184 KB
testcase_12	AC	51 ms 53,724 KB
testcase_13	AC	51 ms 53,724 KB
testcase_14	AC	51 ms 51,676 KB
testcase_15	AC	51 ms 53,720 KB
testcase_16	AC	114 ms 55,972 KB
testcase_17	AC	119 ms 58,876 KB
testcase_18	AC	121 ms 58,672 KB
testcase_19	AC	53 ms 53,728 KB
testcase_20	AC	114 ms 55,884 KB
testcase_21	AC	111 ms 53,912 KB
testcase_22	AC	84 ms 54,688 KB
testcase_23	AC	51 ms 53,716 KB
testcase_24	AC	51 ms 53,724 KB
testcase_25	AC	50 ms 53,732 KB
testcase_26	AC	50 ms 53,724 KB
testcase_27	AC	51 ms 53,740 KB
testcase_28	AC	74 ms 53,804 KB
testcase_29	AC	89 ms 54,376 KB
testcase_30	AC	91 ms 54,600 KB
testcase_31	AC	82 ms 54,368 KB
testcase_32	AC	87 ms 54,332 KB
testcase_33	AC	111 ms 55,968 KB
testcase_34	AC	58 ms 53,800 KB
testcase_35	AC	61 ms 53,756 KB
testcase_36	AC	87 ms 54,852 KB
testcase_37	AC	113 ms 56,612 KB
testcase_38	AC	130 ms 59,128 KB
testcase_39	AC	78 ms 54,328 KB
testcase_40	AC	104 ms 55,852 KB
testcase_41	AC	60 ms 54,312 KB
testcase_42	AC	59 ms 54,312 KB
testcase_43	AC	73 ms 52,344 KB
testcase_44	AC	112 ms 55,992 KB
testcase_45	AC	59 ms 53,768 KB
testcase_46	AC	72 ms 53,808 KB
testcase_47	AC	104 ms 56,040 KB
testcase_48	AC	111 ms 55,916 KB
testcase_49	AC	75 ms 54,432 KB
testcase_50	AC	76 ms 54,328 KB
testcase_51	AC	113 ms 55,872 KB
testcase_52	AC	85 ms 54,376 KB
testcase_53	AC	56 ms 53,800 KB
testcase_54	AC	74 ms 53,932 KB
testcase_55	AC	56 ms 53,748 KB
testcase_56	AC	56 ms 53,748 KB
testcase_57	AC	72 ms 54,332 KB
testcase_58	AC	108 ms 55,948 KB
testcase_59	AC	82 ms 54,376 KB
testcase_60	AC	133 ms 58,940 KB
testcase_61	AC	130 ms 59,324 KB
testcase_62	AC	52 ms 53,724 KB
testcase_63	AC	52 ms 53,720 KB
testcase_64	AC	55 ms 53,744 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.*;
import java.util.*;


public class Main_yukicoder421 {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();
		int m = sc.nextInt();

		int white = 0;
		int black = 0;
		char[][] s = new char[n][];
		for (int i = 0; i < n; i++) {
			s[i] = sc.next().toCharArray();

			for (char c : s[i]) {
				if (c == 'w') {
					white++;
				} else if (c == 'b') {
					black++;
				}
			}
		}

		Dinic di = new Dinic(n * m + 2);
		int source = n * m;
		int sink = source + 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i][j] == 'w') {
					di.addEdge(source, i * m + j, 1);
					if (i > 0 && s[i - 1][j] == 'b') {
						di.addEdge(i * m + j, (i - 1) * m + j, 1);
					}
					if (i < n - 1 && s[i + 1][j] == 'b') {
						di.addEdge(i * m + j, (i + 1) * m + j, 1);
					}
					if (j > 0 && s[i][j - 1] == 'b') {
						di.addEdge(i * m + j, i * m + j - 1, 1);
					}
					if (j < m - 1 && s[i][j + 1] == 'b') {
						di.addEdge(i * m + j, i * m + j + 1, 1);
					}
				} else if (s[i][j] == 'b') {
					di.addEdge(i * m + j, sink, 1);
				}
			}
		}

		int p1 = Math.abs(white - black);
		int p3 = di.getMaxflow(source, sink);
		int p2 = Math.max(white, black) - p1 - p3;

		pr.println(p3 * 100 + p2 * 10 + p1);
	}

	private static class Dinic {
		private static final int INF = Integer.MAX_VALUE;
		ArrayList<Edge>[] edges;
		int n;

		@SuppressWarnings("unchecked")
		Dinic(int n) {
			this.n = n;
			edges = new ArrayList[n];
			for (int ii = 0; ii < n; ii++) {
				edges[ii] = new ArrayList<Edge>();
			}
			checkedTo = new int[this.n];
			level = new int[this.n];
		}

		// i, j:0-indexed
		public void addEdge(int i, int j, int c) {
			edges[i].add(new Edge(j, c, edges[j].size(), false));
			// add reverse edge
			edges[j].add(new Edge(i, c, edges[i].size() - 1, true));
		}

		public int getMaxflow(int s, int t) {
			// initialize flow
			for (int i = 0; i < edges.length; i++) {
				for (Edge e : edges[i]) {
					if (!e.revFlag) {
						e.f = 0;
					} else {
						e.f = e.w;
					}
				}
			}

			int ret = 0;
			while (true) {
				Arrays.fill(level, -1);
				bfs(s);
				if (level[t] == -1) {
					break;
				}

				Arrays.fill(checkedTo, 0);
				int augmentation;
				while ((augmentation = dfs(s, t, INF)) > 0) {
					ret += augmentation;
				}
			}

			return ret;
		}

		private static int[] checkedTo;
		private static int[] level;

		// no capacity edges must be removed
		private void bfs(int s) {
			Queue<Integer> q = new ArrayDeque<Integer>();
			level[s] = 0;
			q.add(s);
			while (!q.isEmpty()) {
				int u = q.remove();
				for (Edge e : edges[u]) {
					if (level[e.v] == -1 && e.w - e.f > 0) {
						level[e.v] = level[u] + 1;
						q.add(e.v);
					}
				}
			}
		}

		// find max flow (less than f), on u -> v path
		// next vertex must has larger level
		private int dfs(int u, int v, int f) {
			if (u == v) {
				return f;
			}

			for (; checkedTo[u] < edges[u].size(); checkedTo[u]++) {
				Edge e = edges[u].get(checkedTo[u]);
				if (level[e.v] > level[u] && e.w - e.f > 0) {
					int a = dfs(e.v, v, Math.min(f, e.w - e.f));
					if (a != 0) {
						e.f += a;
						edges[e.v].get(e.revIndex).f -= a;

						return a;
					}
				}
			}

			return 0;
		}

		private static class Edge {
//			int u; // from
			int v; // to
			int w; // cost
			int f; // flow
			int revIndex; // index of reverse edge
			boolean revFlag; // flag of reverse edge

			Edge(int v, int w, int re, boolean f) {
//				this.u = u;
				this.v = v;
				this.w = w;
				this.f = 0;
				this.revIndex = re;
				this.revFlag = f;
			}
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	@SuppressWarnings("unused")
	private static class Scanner {
		BufferedReader br;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		private boolean isPrintable(int ch) {
			return ch >= '!' && ch <= '~';
		}

		private boolean isCRLF(int ch) {
			return ch == '\n' || ch == '\r' || ch == -1;
		}

		private int nextPrintable() {
			try {
				int ch;
				while (!isPrintable(ch = br.read())) {
					if (ch == -1) {
						throw new NoSuchElementException();
					}
				}

				return ch;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		String next() {
			try {
				int ch = nextPrintable();
				StringBuilder sb = new StringBuilder();
				do {
					sb.appendCodePoint(ch);
				} while (isPrintable(ch = br.read()));

				return sb.toString();
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		int nextInt() {
			try {
				// parseInt from Integer.parseInt()
				boolean negative = false;
				int res = 0;
				int limit = -Integer.MAX_VALUE;
				int radix = 10;

				int fc = nextPrintable();
				if (fc < '0') {
					if (fc == '-') {
						negative = true;
						limit = Integer.MIN_VALUE;
					} else if (fc != '+') {
						throw new NumberFormatException();
					}
					fc = br.read();
				}
				int multmin = limit / radix;

				int ch = fc;
				do {
					int digit = ch - '0';
					if (digit < 0 || digit >= radix) {
						throw new NumberFormatException();
					}
					if (res < multmin) {
						throw new NumberFormatException();
					}
					res *= radix;
					if (res < limit + digit) {
						throw new NumberFormatException();
					}
					res -= digit;

				} while (isPrintable(ch = br.read()));

				return negative ? res : -res;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		long nextLong() {
			try {
				// parseLong from Long.parseLong()
				boolean negative = false;
				long res = 0;
				long limit = -Long.MAX_VALUE;
				int radix = 10;

				int fc = nextPrintable();
				if (fc < '0') {
					if (fc == '-') {
						negative = true;
						limit = Long.MIN_VALUE;
					} else if (fc != '+') {
						throw new NumberFormatException();
					}
					fc = br.read();
				}
				long multmin = limit / radix;

				int ch = fc;
				do {
					int digit = ch - '0';
					if (digit < 0 || digit >= radix) {
						throw new NumberFormatException();
					}
					if (res < multmin) {
						throw new NumberFormatException();
					}
					res *= radix;
					if (res < limit + digit) {
						throw new NumberFormatException();
					}
					res -= digit;

				} while (isPrintable(ch = br.read()));

				return negative ? res : -res;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		float nextFloat() {
			return Float.parseFloat(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			try {
				int ch;
				while (isCRLF(ch = br.read())) {
					if (ch == -1) {
						throw new NoSuchElementException();
					}
				}
				StringBuilder sb = new StringBuilder();
				do {
					sb.appendCodePoint(ch);
				} while (!isCRLF(ch = br.read()));

				return sb.toString();
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new NoSuchElementException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}