单词接龙 (vip) 蓝桥杯

单词接龙 (vip)

如果两个单词有联系，那么就将这两个单词联姻（他俩之间有一条边）吧！如此， 一张单词关系图就建好了， 然后

进行以特定单词为头开始搜索，得到符合要求的最大值！

附代码：

/*************************************************************************
	> File Name: words_dragon.c
	> Author: xzl
	> Mail:xiaolongqdu@gmail.com 
	> Created Time: 2014年03月20日 星期四 14时46分13秒
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char str[25][10];
int map[25][25];
int n, visited[25], max_sum;
int length[25];

void init();
void dfs(int i, int v);
int change(char str1[], char str2[]);

int main(){
    
    int i, j;
    int len1, len2, num, front, end, sum = 0;
    char ch;

    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%s", str[i]);   
        length[i] = strlen(str[i]);
    }
    
    scanf("%c", &ch);

    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            map[i][j] = change(str[i], str[j]);
        }
    }
    
    for(i = 0; i < n; i++){
        if(str[i][0] == ‘a‘){
            init();
            max_sum = 0;
            dfs(0, length[0]);
            if(sum < max_sum){
                sum = max_sum;   
            }
        }
    }

    printf("%d\n", sum);
}

int change(char str1[], char str2[]){

    int i, j;
    int len1 = strlen(str1), len2 = strlen(str2);
    int front1, front2;
    for(i = 0; i < len1; i++){
        front1 = i; front2 = 0; 
        len2 = strlen(str2);
        while(str1[front1] == str2[front2] && str1[front1] && str2[front2]){
            front1 ++; front2++;
        }
        if(front1 == len1 && i == 0){
            return 0;
        }
        else if(front1 == len1 && front2 == len2){
            return 0;
        }
        else if(front1 == len1 && i != 0 && front2 != len2){
            return (len1 - i);
        }
    }
    return 0;
}

void dfs(int v, int sum){
    
    int i, var;
    
    if(sum > max_sum){
        max_sum = sum;
    }
    
    for(i = 0; i < n; i++){
        if(map[v][i] != 0 && visited[i] > 0){
            visited[i]--;
            dfs(i, sum + length[i] - map[v][i]);
            visited[i]++;
        }   
    }
}

void init(){
    int i;
    for(i = 0; i <= n; i++){
        visited[i] = 2;
    }
}

单词接龙 (vip) 蓝桥杯,布布扣,bubuko.com

单词接龙 (vip) 蓝桥杯

原文：http://blog.csdn.net/huntinggo/article/details/21628163