Google Code Jam Round 1C 2014 - Problem B. Reordering Train Cars

reordering.c

// Brute force searching algorithm
// I rewrite it into a *C code* with some comments for beginners
// Originally from https://gist.github.com/autekroy/bc5ea2c82fb74a5bb2b5
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
long long ans;
int visit[101], check[500];
int N, len[101];
char s[101][101], str[100000];
 
int judge(char* str) // How to judge? If a character appears once, it must appear continously after the first appearance.
{
    int len = strlen(str);
    int i;
 
    char tmp1, tmp2;
    tmp1 = str[0];
    
    memset(check, 0, sizeof(check));
    check[tmp1] = 1;
    for(i = 1; i < len; i++)
    {
        tmp2 = str[i];
        if(tmp1 == tmp2 )
            continue;
        if(tmp1 != tmp2)
        {
            if(check[tmp2])//appear before
		return 0;

            tmp1 = tmp2;
            check[tmp2] = 1;
            continue;
        }
    }
    return 1;
}
void dfs(int now, int p, int index) //now is the current node, p is the depth of search, index is of concatenated string
{
    int i;
    for(i = 0; i < len[now]; i++)
    {
        str[index] = s[now][i]; // push current node into string
        index++;
    }
    
    if(p == N) // if to the end of search
    {
        str[index] = '\0'; // give string a nice ending
        if(judge(str)) // If the current solution string is legitimate
        {
	  ans ++;
	  if(ans > 1000000007)
	    ans -= 1000000007;
        }
        return;
    }
 
    for(i = 0; i< N; i++)  // Keep searching
    {
        if(!visit[i])   //If some node is not searched yet
        {
            visit[i] = 1;
            dfs(i, p+1, index);
            visit[i] = 0;
        }
    }
}
 
int main()
{
    int T; // Number of test cases
    int testCase,i;
    
    scanf("%d", &T);
 
    for(testCase = 1; testCase <= T; testCase++)
    {
        scanf("%d", &N); //Number of nodes
        ans = 0; // Number of possible solutions
 
        for(i = 0; i < N; i++)
        {
            scanf("%s", s[i]); //Store the nodes in s
            len[i] = strlen(s[i]); //Store the length in len --> save time cost
        }
        memset(visit, 0, sizeof(visit));
 
        for(i = 0; i < N; i++)
        {
            visit[i] = 1; // Start from every node, depth-first-search every possible solutions
            dfs(i, 1, 0); // dsf([start point], [depth],[index])
            visit[i] = 0; // Restore
        }
 
        printf("Case #%d: ", testCase);
        printf("%lld\n", ans);
    }
    return 0;
}