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; }