【题解】UVa 140【Bandwidth】

背景

这题深搜输入都好烦

分析

其实这里可以完全爆搜过去的,枚举全排列就好了,这里加一个小剪枝。

代码

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

char s[10], str[10];
int vis[26], map[26][26];
int n, Max;

void dfs(int x){
    int min;
    if (x >= n){
        min = 0;    
        for(int i = 0; i < n; i++)  
            for(int j = i + 1; j < n; j++)  
                if ((map[str[i] - 'A'][str[j] - 'A'] == 1) && (j - i > min))    
                    min = j - i;
        if (min < Max){
            Max = min;  
            strcpy(s, str); 
        }   
        if((min == Max) && strcmp(s, str) > 0)
            strcpy(s, str); 
        return; 
    }
    for(int i = 0; i < 26; i++)
        if (vis[i] == 1){
            vis[i] = 0; 
            str[x] = i + 'A';   
            dfs(x + 1); 
            vis[i] = 1;
        }
}

int main(){
    char c, ch;
    while (scanf("%c", &c) && c != '#'){
        memset(map, 0, sizeof(map));            
        memset(vis, 0, sizeof(vis));    
        while (scanf("%c", &ch) && ch != '\n'){
            if (isalpha(ch)){   
                map[c - 'A'][ch - 'A'] = 1;     
                map[ch - 'A'][c - 'A'] = 1; 
                vis[c - 'A'] = 1;   
                vis[ch - 'A'] = 1;
            }   
            if(ch == ';')   
                scanf("%c", &c);
        }   
    n = 0, Max = 99999;
    for(int i = 0; i < 26; i++)
        if (vis[i])
            s[n++] = i + 'A';
    s[n] = '\0';
    str[n] = '\0';
    dfs(0); 
    for(int i = 0; s[i] != '\0'; i++)
        printf("%c ", s[i]);
    printf("-> %d\n" , Max);    
    }
    return 0;
}