結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-09-09 11:50:15 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 207 ms / 2,000 ms |
| コード長 | 6,167 bytes |
| コンパイル時間 | 6,715 ms |
| コンパイル使用メモリ | 92,136 KB |
| 実行使用メモリ | 56,224 KB |
| 最終ジャッジ日時 | 2024-09-23 07:04:30 |
| 合計ジャッジ時間 | 13,587 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 65 |
ソースコード
package No400番台;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;public class Q421_0 {int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int h, w;char[][] choco;int[][] comp;HashMap<Integer, Pair> map = new HashMap<>();@SuppressWarnings("unchecked")void solver() {h = ni();w = ni();choco = new char[h][w];for (int i = 0; i < h; i++) {choco[i] = ns().toCharArray();}comp = new int[h][w];for (int i = 0; i < h; i++) {Arrays.fill(comp[i], -1);}int color = 0;int ans = 0;int odd = 0, even = 0;ArrayList<Integer>[] g = new ArrayList[h * w];for (int i = 0; i < h * w; i++) {g[i] = new ArrayList<>();}for (int y = 0; y < h; y++) {for (int x = 0; x < w; x++) {if (on_filed(x, y) && comp[y][x] == -1) {ArrayDeque<Pair> que = new ArrayDeque<>();que.add(new Pair(x, y));while (!que.isEmpty()) {Pair p = que.poll();if (comp[p.y][p.x] != -1)continue;comp[p.y][p.x] = color;if ((p.x + p.y) % 2 == 0)even++;elseodd++;for (int i = 0; i < 4; i++) {int nx = p.x + dx[i];int ny = p.y + dy[i];if (on_filed(nx, ny) && comp[ny][nx] == -1) {int a = id(p.x, p.y);int b = id(nx, ny);map.put(a, new Pair(p.x, p.y));map.put(b, new Pair(nx, ny));g[a].add(b);g[b].add(a);que.add(new Pair(nx, ny));}}}color++;}}}int the_number_of_matchings = bipartiteMatching(g, (h * w + 1) / 2);ans += the_number_of_matchings * 100;even -= the_number_of_matchings;odd -= the_number_of_matchings;// show_comp();int common = Math.min(even, odd);ans += common * 10;even -= common;odd -= common;ans += even + odd;out.println(ans);}int id(int x, int y) {if ((y + x) % 2 == 0)return (y * w + x) / 2;elsereturn (y * w + x) / 2 + (h * w - 1) / 2 + 1;}boolean on_filed(int x, int y) {if (0 <= x && x < w && 0 <= y && y < h && choco[y][x] != '.') {return true;} elsereturn false;}class Pair {int x;int y;Pair(int x, int y) {this.x = x;this.y = y;}}boolean augment(ArrayList<Integer>[] g, int u, Integer[] matchTo, Boolean[] visited) {if (u < 0)return true;for (int v : g[u]) {if (!visited[v]) {visited[v] = true;if (augment(g, matchTo[v], matchTo, visited)) {matchTo[u] = v;matchTo[v] = u;return true;}}}return false;}int bipartiteMatching(ArrayList<Integer>[] g, int L) {final int n = g.length;Integer[] matchTo = new Integer[n];Arrays.fill(matchTo, -1);matching = new ArrayList<>();int match = 0;for (int i = 0; i < L; i++) {Boolean[] visited = new Boolean[n];Arrays.fill(visited, false);if (augment(g, i, matchTo, visited))match++;}for (int i = 0; i < L; i++) {if (matchTo[i] > 0)matching.add(new Edge(i, matchTo[i]));}return match;}ArrayList<Edge> matching;class Edge {int a;int b;Edge(int a, int b) {this.a = a;this.b = b;}}void show_comp() {for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {System.out.print((comp[i][j] == -1 ? "#" : comp[i][j]) + " ");}System.out.println();}}static InputStream is;static PrintWriter out;static String INPUT = "";public static void main(String[] args) throws Exception {is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);new Q421_0().solver();out.flush();}static long nl() {try {long num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}static char nc() {try {int b = skip();if (b == -1)return 0;return (char) b;} catch (IOException e) {}return 0;}static double nd() {try {return Double.parseDouble(ns());} catch (Exception e) {}return 0;}static String ns() {try {int b = skip();StringBuilder sb = new StringBuilder();if (b == -1)return "";sb.append((char) b);while (true) {b = is.read();if (b == -1)return sb.toString();if (b <= ' ')return sb.toString();sb.append((char) b);}} catch (IOException e) {}return "";}public static char[] ns(int n) {char[] buf = new char[n];try {int b = skip(), p = 0;if (b == -1)return null;buf[p++] = (char) b;while (p < n) {b = is.read();if (b == -1 || b <= ' ')break;buf[p++] = (char) b;}return Arrays.copyOf(buf, p);} catch (IOException e) {}return null;}public static byte[] nse(int n) {byte[] buf = new byte[n];try {int b = skip();if (b == -1)return null;is.read(buf);return buf;} catch (IOException e) {}return null;}static int skip() throws IOException {int b;while ((b = is.read()) != -1 && !(b >= 33 && b <= 126));return b;}static boolean eof() {try {is.mark(1000);int b = skip();is.reset();return b == -1;} catch (IOException e) {return true;}}static int ni() {try {int num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}}