結果
問題 | No.348 カゴメカゴメ |
ユーザー | 37zigen |
提出日時 | 2016-06-14 21:37:46 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,958 bytes |
コンパイル時間 | 2,738 ms |
コンパイル使用メモリ | 81,596 KB |
実行使用メモリ | 301,188 KB |
最終ジャッジ日時 | 2024-10-09 13:44:36 |
合計ジャッジ時間 | 34,628 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 164 ms
41,568 KB |
testcase_05 | AC | 200 ms
43,584 KB |
testcase_06 | AC | 132 ms
41,412 KB |
testcase_07 | AC | 132 ms
41,148 KB |
testcase_08 | AC | 131 ms
41,108 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 134 ms
41,572 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 833 ms
100,948 KB |
testcase_16 | AC | 131 ms
41,332 KB |
testcase_17 | AC | 131 ms
41,192 KB |
testcase_18 | AC | 132 ms
41,120 KB |
testcase_19 | AC | 132 ms
40,912 KB |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 119 ms
40,228 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, true, edges, grid, ds)); } // b=true:一つ外が囲まれていない // b=false:一つ外が囲まれている 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; for (Iterator<Integer> it = edges[i].iterator(); it.hasNext();) { int j = it.next(); if (j != p) { int x = rec(j, i, true, edges, grid, ds); int y = rec(j, i, false, edges, grid, ds); u += x; 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; } } }