何时“苏醒”? (湖南省第二届程序设计大赛) -- 编程驿站-- 编程爱好者博客

何时“苏醒”?

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB

Total submit users: 61, Accepted users: 41

Problem 10843 : No special judgement

Problem description

人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。 “苏醒”后的分区不会再转入“睡眠”状态。
有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？

Input

输入文件的第1行仅包含1个整数M，取值范围是[3, 26]，它表示病人大脑的分区数。
第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。
第3行包含3个相邻的大写英文字母，分别代表刚刚同时“苏醒”的3个分区。
第4行中包含N个用空格分割的字符串，每个字符串包含2个大写英文字母，分别代表2个相连接的分区。

Output

如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行：
“WAKE UP IN n YEARS” （其中n指分区全部“苏醒”需要的年数）
如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行：
“THIS BRAIN NEVER WAKES UP”

Sample Input

6 
11 
HAB 
AB AC AH BD BC BF CD CF CH DF FH

Sample Output

WAKE UP IN 3 YEARS

Problem Source

湖南省第二届程序设计大赛

/// 这个题比较简单，只要设一个二维数组表示分区的连接情况
/// 用一维数组记录已经苏醒的分区

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    while(cin>>n){
        char buf[4];
        int m,y,i,j,w,t;
        bool status[26] = {false},a[26][26] = {false};
        cin>>m;
        cin>>buf;
        status[buf[2]-'A']=status[buf[1]-'A']=status[buf[0]-'A']=true;
        for(i=0; i<m; i++){
            cin>>buf;
            a[buf[0]-'A'][buf[1]-'A']=a[buf[1]-'A'][buf[0]-'A']=true;
        }
        bool flag=true;
        vector<int> wake;
        for(w=3,y=0; flag && w<m; y++){
            wake.clear();
            for(i=0; i<26; i++){
                if(status[i])
                    continue;
                for(t=j=0; j<26; j++){
                    if(a[i][j] && status[j])
                        t++;
                    if(t>=3)
                        break;
                }
                if(j<26)
                    wake.push_back(i);
            }
            if(wake.empty())
                break;
            for(i=0; i<wake.size(); i++){
                w++;
                status[wake[i]]=true;
            }
        }
        if(w==n)
            cout<<"WAKE UP IN "<<y<<" YEARS"<<endl;
        else
            cout<<"THIS BRAIN NEVER WAKES UP"<<endl;
    }
    return 0;
}

博客介绍

正文

何时“苏醒”? (湖南省第二届程序设计大赛)2007-08-19 10:00:00

评论