結果
問題 | No.348 カゴメカゴメ |
ユーザー | 37zigen |
提出日時 | 2016-06-14 21:53:15 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,965 bytes |
コンパイル時間 | 2,283 ms |
コンパイル使用メモリ | 81,980 KB |
実行使用メモリ | 315,668 KB |
最終ジャッジ日時 | 2024-10-09 13:46:13 |
合計ジャッジ時間 | 33,458 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,261 ms
171,712 KB |
testcase_01 | AC | 157 ms
41,820 KB |
testcase_02 | WA | - |
testcase_03 | AC | 1,859 ms
315,668 KB |
testcase_04 | AC | 156 ms
42,120 KB |
testcase_05 | AC | 195 ms
44,140 KB |
testcase_06 | AC | 133 ms
41,612 KB |
testcase_07 | AC | 131 ms
41,636 KB |
testcase_08 | AC | 115 ms
41,660 KB |
testcase_09 | AC | 134 ms
41,424 KB |
testcase_10 | WA | - |
testcase_11 | AC | 128 ms
40,520 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 829 ms
100,680 KB |
testcase_16 | AC | 126 ms
41,648 KB |
testcase_17 | AC | 128 ms
41,868 KB |
testcase_18 | AC | 130 ms
41,728 KB |
testcase_19 | AC | 124 ms
40,588 KB |
testcase_20 | AC | 141 ms
41,840 KB |
testcase_21 | AC | 136 ms
41,848 KB |
testcase_22 | AC | 130 ms
41,508 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | WA | - |
testcase_51 | WA | - |
testcase_52 | WA | - |
ソースコード
package yukicoder; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.Scanner; 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; int 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; int xx = j + dx; if (xx == -1 || yy == -1 || xx == M || yy == N) 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]; for (int i = 0; i < N * M; 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 vertices int[] 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>y d[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; } } }