HDU1181 变形课 【深搜、广搜、弗洛伊德(Floyd)算法】

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 29 日

水题,练习练习,复习复习。。。。

大意:根据所给字母收尾字母建图的链接边。然后……搜吧,另外还可以练习一下Floyd算法。。

#include<cstdio>  
#include <cstring>  
#include<string>  
#include <queue>  
using namespace std;  
int map[27][27],flag;  
int visted[27];  
void dfs(int pos){  
    if(flag) return;  
    if(pos==12){ flag=1;return;}  
    for (int i=0;i<26;i++){  
        if(map[pos][i]) dfs(i);  
    }  
}  
void bfs(int pos){  
    if(flag) return;  
    queue<int> que;  
    que.push(pos);  
    while(!que.empty()){  
        for (int i=0;i<26;i++){  
            if(map[que.front()][i]==1 && visted[i]==0) {  
                que.push(i);  
                visted[i]=1;  
                if(i==12) {flag=1;return;}  
            }  
        }  
        que.pop();  
    }  
}  
int main(){  
    freopen("1.txt","r",stdin);  
    char str[30];  
    while(scanf("%s",str)!=EOF){  
        if(str[0]=='0'){  
            flag=0;  
            bfs(1);  
            if(flag) printf("Yes.\n");  
            else printf("No.\n");  
            memset(map,0,sizeof(map));  
            memset(visted,0,sizeof(visted));  
            continue;  
        }  
        map[(int)(str[0]-'a')][(int)(str[strlen(str)-1]-'a')]=1;  
    }  
}  

一下为Floyd算法的此题改造版:

#include <stdio.h>  
#include <string.h>  
const int N=28 ;  
int map[N][N] ;  
void Floyd( )  
{  
    int i, j, k ;  
    for( k=0; k<26; ++k )  
        for( i=0; i<26; ++i )  
            for( j=0; j<26; ++j )  
                map[i][j] = map[i][j] || ( map[i][k] && map[k][j] ) ;  
}  
int main()  
{  
    freopen("1.txt","r",stdin);  
    int len ;  
    char a[2000] ;  
    while( EOF != scanf("%s",a) ){  
        if( a[0] == '0' ){  
            Floyd( ) ;  
            if( map[1][12] )  
                printf("Yes.\n") ;  
            else  
                printf("No.\n") ;  
            memset( map, 0, sizeof(map) ) ;  
            continue ;  
        }  
        len = strlen( a ) ;  
        map[a[0]-'a'][a[len-1]-'a'] = 1 ;  
    }  
    return 0 ;  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日