题解 | #[NOIP2000]单词接龙#

忘记局部变量的回溯了，调了1个小时~

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

int num;
char input[20][100] = {0};
int hash[20] = {0};
int max_len;

int my_strcmp(char *str1, int size1, char *str2, int size2)
{
    int left, right;
    int flag;
    int minLeftVal = (size1 == 1) ? 0 : 1;
    int i;
    
    //printf("%s, %d, %s, %d\n", str1, size1, str2, size2);
    
    for (left = size1 - 1; left >= minLeftVal; left--) {
        right = left;
        flag = 0;
        for (i = 0; (i < size2) && (right < size1); i++, right++) {
            if (str1[right] != str2[i]){
                flag = 1;
            }
        }
        
        if ((flag == 0) && (right == size1) && (i != size2)) {
            //printf("%s, %s, comm len=%d\n", str1, str2, size1 - left);
            return size1 - left;
        }
    }
    
    return 0;
}

void dfs(char *currStr, int currLen, int allLen)
{
    int comm_len;
    int currInputLen;

    for (int i = 0; i < num; i++) {
        if (hash[i] > 0) {
            currInputLen = strlen(input[i]);
            comm_len = my_strcmp(currStr, currLen, input[i], currInputLen);
            if (comm_len > 0) {
                hash[i]--;
                allLen += currInputLen - comm_len;
                //printf("%s, %s, allLen=%d, currLen=%d, commLen=%d\n", currStr, input[i], allLen, currInputLen, comm_len);
                max_len = fmax(max_len, allLen);
                dfs(input[i], strlen(input[i]), allLen);
                allLen -= currInputLen - comm_len;  // 循环内的局部变量，记得回溯
                hash[i]++;
            }
        }
    }
}

int main(void)
{   
    char start[10] = {0};
    int start_len;
    max_len = 0;
    
    scanf("%d", &num);
    
    for (int i = 0; i < num; i++) {
        hash[i] = 2;
        scanf("%s", input[i]);
    }
    
    scanf("%s", start);
    start_len = strlen(start);
    
    dfs(start, start_len, start_len);
    
    printf("%d\n", max_len);
    
    return 0;
}