#264683 (C++11) No.697 池の数はいくつか

• 問題: No.697 池の数はいくつか
• ユーザー: horiesiniti
• 提出日時: 2018-06-11 03:13:06
• 言語: C++11 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 654 ms / 6,000 ms
• コード長: 1,067 bytes
• コンパイル時間: 628 ms
• コンパイル使用メモリ: 86,032 KB
• 実行使用メモリ: 37,624 KB
• 最終ジャッジ日時: 2026-05-08 13:54:32
• 合計ジャッジ時間: 6,796 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 3
other	AC * 32

ソースコード

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <set>

using namespace std;
vector<int> vec;
set<int> ss;

int f(int p){
	if(p==vec[p]){
		return p;
	}else{
		int p2=f(vec[p]);
		vec[p]=p2;
		return p2;
	}
}


int main() {
	// your code goes here
	int h,w;
	int ms[2][3001];
	int cs[2][3001];
	int c=0;
	memset(cs,0,sizeof(cs));
	memset(ms,0,sizeof(ms));
	scanf("%d %d",&h,&w);
	for(int y=0;y<h;y++){
		int now=y%2;
		int old=(y+1)%2;
		for(int x=0;x<w;x++){
			scanf("%d",&ms[now][x]);
		}
		for(int x=0;x<w;x++){
			if(ms[now][x]==0)continue;
			
			int ml,mu;
			if(x-1<0){
				ml=0;
			}else{
				ml=ms[now][x-1];
			}
			if(y-1<0){
				mu=0;
			}else{
				mu=ms[old][x];
			}
			if(ml==0&&mu==0){
				vec.push_back(c);
				cs[now][x]=c;
				c++;
			}else if(ml==0){
				cs[now][x]=cs[old][x];
			}else if(mu==0){
				cs[now][x]=cs[now][x-1];
			}else{
				cs[now][x]=cs[old][x];
				vec[f(cs[now][x-1])]=f(cs[old][x]);
			}
		}
	}
	for(int i=0;i<vec.size();i++){
		ss.insert(f(i));
	}
	printf("%d\n",ss.size());
	return 0;
}