UVa-10507 : Waking up brain

問題概要

ノード数N(<26)の無向グラフがあり、そのうちいくつかは色が塗られている。各頂点について、隣接するノードに色がついているものが3つ以上あれば自分も色が塗られる。全ての頂点が色が塗られるか、塗られるなら何ターンかかるかを求める問題。

解法

シミュレーションするだけ。updateを検出するもよし。26ターン回すもよし。プレゼンテーションエラーに注意。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 26;
int N;

bool awake[MAX_N], next_awake[MAX_N];
bool graph[MAX_N][MAX_N];

void init(){
	memset(awake, false, sizeof(awake));
	memset(graph, false, sizeof(graph));

	int M;
	scanf("%d ", &M);
	char buf[30];
	scanf("%[^\n]%*c", buf);
	for(int i=0, L=strlen(buf); i<L; i++){
		awake[buf[i]-'A'] = true;
	}

	for(int i=0; i<M; i++){
		scanf("%[^\n]%*c", buf);
		graph[buf[0]-'A'][buf[1]-'A'] = true;
		graph[buf[1]-'A'][buf[0]-'A'] = true;
	}
}

int solve(){
	for(int k=0; k<MAX_N; k++){
		if(count(awake, awake+MAX_N, true) == N){
			return k;
		}
		memset(next_awake, false, sizeof(next_awake));
		for(int i=0; i<MAX_N; i++){
			int cnt = 0;
			for(int j=0; j<MAX_N; j++)if(awake[j] && graph[i][j]){
				cnt++;
			}
			if(cnt >= 3){
				next_awake[i] = true;
			}
		}
		for(int i=0; i<MAX_N; i++){
			if(next_awake[i]){
				awake[i] = true;
			}
		}
	}

	return -1;
}

int main(){
	bool first = true;
	while(scanf("%d", &N)!=EOF){
		init();
		int ans = solve();
		if(ans == -1){
			puts("THIS BRAIN NEVER WAKES UP");
		}
		else{
			printf("WAKE UP IN, %d, YEARS\n", ans);
		}
	}

	return 0;
}