結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー 37zigen
提出日時 2016-06-14 18:21:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 2,745 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 896 ms
コンパイル使用メモリ 76,404 KB
実行使用メモリ 814,436 KB
最終ジャッジ日時 2024-10-09 13:34:43
合計ジャッジ時間 5,584 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 5 MLE * 1 -- * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <vector>
#include <utility>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
struct DJSet{
	vector<int> data;
	void init(int n){
		data.assign(n, -1);
	}
	bool unionSet(int x, int y){
		x = root(x);
		y = root(y);
		if (x != y){
			if (data[y]<data[x]){
				swap(x, y);
			}
			data[x] += data[y];
			data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y){
		return root(x) == root(y);
	}
	int root(int x){
		return data[x]<0 ? x : root(data[x]);
	}
	int size(int x){
		return -data[root(x)];
	}
};
vector<int> memo;
int rec(int i, int p, bool b, const vector<vector<int>> &g, const vector<string>grid, DJSet &ds){
	int &r = memo[i * 2 + b];
	if (r == -2)cerr << "error" << endl;
	if (r != -1)return r;
	if (grid[i / grid[0].size()][i%grid[0].size()] == '.'){
		int t = 0;
		for (int j = 0; j < g[i].size(); j++){
			if (g[i][j] != p){
				t += rec(g[i][j], i, b,g, grid, ds);
			}
		}
		r = t;
	}
	else{
		int t = 0, u = 0;
		for (int j = 0; j < g[i].size(); j++){
			int to = g[i][j];
			if (to != p)
			{
				int x = rec(to, i, false, g, grid, ds);
				int y = rec(to, i, true, g, grid, ds);
				t += max(x, y);
				u += y;
			}
		}
		r = t;
		if (!b){
			r = max(r, u + ds.size(i));
		}
	}
	
	return r;
}
int main(){
	int N, M;
	while (~scanf("%d%d", &N, &M)){
		vector<string> grid(N + 2);
		grid[0] = string(M, '.'); 
		for (int i = 0; i < M; i++){
			cin >> grid[i+1];
		}
		for (int i = 0; i < N + 2; i++){
			grid[i] = "." + grid[i] + ".";
		}
		N += 2;
		M += 2;
		DJSet ds;
		ds.init(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 || dy){
							int yy = i + dy;
							int xx = j + dx;
							if (yy == -1 || xx == -1 || yy == N || xx == M)continue;
							if (grid[i][j] = '.'&&abs(dx) + abs(dy) > 1)continue;
							if (grid[i][j] != grid[yy][xx])continue;
							ds.unionSet(i*M + j, yy*M+xx);

						}
					}
				}
			}
		}
		vector<vector<int>> g(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 || dy){
							int yy = i + dy;
							int xx = j + dx;
							if (yy == -1 || xx == -1 || yy == N || xx == M)continue;
							if (abs(dx) + abs(dy) > 1)continue;
							if (grid[i][j] != grid[yy][xx]){
								g[ds.root(i*M + j)].push_back(ds.root(yy*M + j));
							}
						}
					}
				}
			}
		}
		for (int i = 0; i < N*M; i++){
			vector<int> &v = g[i];
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
		}
		memo.assign(N*M * 2, -1);
		int ans=rec(ds.root(N*M-1),-1,false,g,grid,ds);
		printf("%d\n", ans);
		
	}
	return 0;
}
0