UVa 291 The House Of Santa Claus

解題：用dfs找Euler Trail
Code：

 1  #include<stdio.h>

 2  #include<stdlib.h>

 3  #include<algorithm>

 4  #include<iostream>

 5  #include<string.h>

 6  using namespace std;

 7  int adj[8][8];

 8  void initial()

 9  {

10      adj[1][2]=1,adj[1][3]=1,adj[1][5]=1;

11      adj[2][1]=1,adj[2][3]=1,adj[2][5]=1;

12      for(int i=1; i<=5; i++) if(i!=3) adj[3][i]=1;

13      for(int i=1; i<=5; i++) if(i!=5) adj[5][i]=1;

14      adj[4][5]=1,adj[4][3]=1;

15  }

16  int arr[10];

17  bool dfs(int s,int cnt)

18  {

19      arr[cnt]=s;

20      if(cnt==8)

21      {

22          for(int i=0;i<9;i++)

23          {

24              cout<<arr[i];

25          }

26          cout<<endl;

27      }

28      for(int i=1;i<=5;i++)

29      {

30          if(adj[s][i]>0)

31          {

32              adj[s][i]=adj[i][s]=0;

33              dfs(i,cnt+1);

34              adj[s][i]=adj[i][s]=1;

35          }

36      }

37      return false;

38  }

39  int main()

40  {

41      memset(adj,0,sizeof(adj));

42      initial();

43      dfs(1,0);

44      return 0;

45  }