結果
問題 | No.348 カゴメカゴメ |
ユーザー |
|
提出日時 | 2016-06-14 23:18:49 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,176 ms / 2,000 ms |
コード長 | 5,079 bytes |
コンパイル時間 | 2,711 ms |
コンパイル使用メモリ | 81,516 KB |
実行使用メモリ | 169,140 KB |
最終ジャッジ日時 | 2024-10-09 13:50:23 |
合計ジャッジ時間 | 26,153 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 53 |
ソースコード
package yukicoder;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.HashSet;import java.util.Iterator;import java.util.Set;public class Main {public static void main(String[] args) {new Main().solver();}void solver() {Scanner sc = new Scanner(System.in);int N, M;N = sc.nextInt();M = sc.nextInt();char[][] grid = new char[N + 2][M + 2];for (int i = 0; i < M + 2; i++) {grid[0][i] = '.';grid[N + 1][i] = '.';}for (int i = 0; i < N + 2; i++) {grid[i][0] = '.';grid[i][M + 1] = '.';}for (int i = 0; i < N; i++) {String s = sc.next();for (int j = 0; j < M; j++) {grid[i + 1][j + 1] = s.charAt(j);}}N += 2;M += 2;DJSet ds = new DJSet(N * M);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {for (int dx = -1; dx <= 1; dx++) {for (int dy = -1; dy <= 1; dy++) {if (dx != 0 || dy != 0) {int yy = i + dy, xx = j + dx;if (yy == -1 || xx == -1 || yy == N || xx == M)continue;if (grid[i][j] == '.' && Math.abs(dx) + Math.abs(dy) > 1)continue;if (grid[i][j] != grid[yy][xx])continue;ds.setUnion(i * M + j, yy * M + xx);}}}}}ArrayList<Integer>[] edges = new ArrayList[N * M];for (int i = 0; i < N * M; i++)edges[i] = new ArrayList<Integer>();for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {for (int dx = -1; dx <= 1; dx++) {for (int dy = -1; dy <= 1; dy++) {if (dy != 0 || dx != 0) {int yy = i + dy, xx = j + dx;if (xx == -1 || yy == -1 || xx == M || yy == N)continue;if (Math.abs(dx) + Math.abs(dy) > 1)continue;if (grid[i][j] != grid[yy][xx]) {edges[ds.root(i * M + j)].add(ds.root(yy * M + xx));}}}}}}for (int i = 0; i < N * M; i++) {Set<Integer> set = new HashSet<Integer>();for (int j = 0; j < edges[i].size(); j++) {set.add(edges[i].get(j));}edges[i].clear();for (Iterator<Integer> it = set.iterator(); it.hasNext();) {edges[i].add(it.next());}}memo = new int[2 * N * M + 10];for (int i = 0; i < 2 * N * M + 10; i++)memo[i] = -1;System.out.println(rec(ds.root(0), -1, false, edges, grid, ds));}int rec(int i, int p, boolean b, ArrayList<Integer>[] edges, char[][] grid, DJSet ds) {int r = memo[2 * i + (b ? 1 : 0)];if (r == -2)throw new AssertionError("error");if (r != -1)return r;r = -2;if (grid[i / grid[0].length][i % grid[0].length] == '.') {int t = 0;for (Iterator<Integer> it = edges[i].iterator(); it.hasNext();) {int j = it.next();if (j != p) {t += rec(j, i, b, edges, grid, ds);}}r = t;} else {int t = 0, u = 0;// b=true:一つ外が囲まれている// b=false:一つ外が囲まれていないfor (Iterator<Integer> it = edges[i].iterator(); it.hasNext();) {int j = it.next();if (j != p) {int x = rec(j, i, false, edges, grid, ds);int y = rec(j, i, true, edges, grid, ds);u += y;t += Math.max(x, y);}}r = t;u += ds.size(i);if (!b) {r = Math.max(r, u);}}return memo[2 * i + (b ? 1 : 0)] = r;}int[] memo;class DJSet {int n;// the number of verticesint[] d;DJSet(int n) {this.n = n;d = new int[n];Arrays.fill(d, -1);}int root(int x) {return d[x] < 0 ? x : root(d[x]);}boolean setUnion(int x, int y) {x = root(x);y = root(y);if (x != y) {if (x < y) {int d = x;x = y;y = d;}// x>yd[y] += d[x];d[x] = y;}return x != y;}boolean equiv(int x, int y) {return root(x) == root(y);}// xを含む木のNodeの数int size(int x) {return d[root(x)] * (-1);}// 連結グラフの数int count() {int ct = 0;for (int u : d) {if (u < 0)ct++;}return ct;}}private static class Scanner {BufferedReader br;Iterator<String> it;Scanner(InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext())it = Arrays.asList(br.readLine().split(" ")).iterator();return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}