HDU1181 变形课(传递闭包)

December 19, 2015

题目链接

题意:给出一组单词接龙,第二个词的首字母是第一个单词的末字母,问能否利用给出的这组单词从 b 到 m。

题解:二维数组 pic 中每个位置分别代表一个单词,首尾字母代表坐标,每读入一个单词标记为 1,其余是 0。最后判断一下 bm 这个坐标里的数是否为 1 即可。这题注意一下多组数据的读入(我 WA 了一次。。)

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
int pic[50][50];
int main(){
    //freopen("a.txt", "r", stdin);
    string s;
    while(cin >> s){
        if(s[0] != '0'){
            int l = s.length();
            pic[s[0]-'a'][s[l-1]-'a'] = 1;
        }else{
            for(int k = 0; k <= 26; k++){
                for(int i = 0; i <= 26; i++){
                    if(pic[i][k]){
                        for(int j = 0; j <= 26; j++){
                            if(pic[k][j])
                                pic[i][j] = 1;
                        }
                    }
                }
            }
            if(pic[1][12]) cout << "Yes." << endl;
            else cout << "No." << endl;
            memset(pic, 0, sizeof(pic));
        }
    }
    return 0;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]