結果

問題 No.348 カゴメカゴメ
ユーザー 37zigen37zigen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 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);
}
// xNode
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);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0