摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DFS

由於N<=10 由於偷懶直接用相鄰矩陣做暴力解

/********************************************************/

#include<stdlib.h>
#include<stdio.h>
int map[27][27]={0},used[27]={0},MIN=2147483647;
void DFS(int now,int start,int L)
{
   int a;
   if(L>MIN) return;
   for(a=0;a<26;a++)
       if(used[a]==0&&map[now][a]==1)
          {
             used[a]=1;
             DFS(a,start,L+1);
             used[a]=0;
          }
       else
          {
             if(map[now][a]==1&&a==start&&L<MIN)
                MIN=L;
          }
}
main()
{
  int N,a,b;
  char s[10];
  scanf("%d",&N);
  while(N--)
       scanf("%s",s),map[s[0]-'A'][s[1]-'A']=1;
  for(a=0;a<26;a++)
      {
        used[a]=1;
        DFS(a,a,1);
        used[a]=0;
      }
  if(MIN!=2147483647)
       printf("%d\n",MIN);
  else printf("0\n");
  return 0;
}