SDUT 2405 Strange Square(DFS)

10935 ワード

タイトルリンク
省試合ウォーミングアップ試合C問題、当時はまだDFSができませんでした.の私は直接暴力で9点を挙げて、小さな枝を加えて、繰り返しの操作を判断することが重要です...DFSでこのレイヤでこの数を検索したかどうかを記録する配列を開きます.Caseを忘れ始め、2 Y.
 1 #include <stdio.h>

 2 #include <string.h>

 3 int p[10],o[10],k[10],z;

 4 void dfs(int x)

 5 {

 6     int sum,sum1,i,j,a;

 7     int q[10],w;

 8     if(x > 9)

 9     {

10         sum = k[1] + k[2] + k[3];

11         sum1 = k[1] + k[4] + k[7];

12         if(sum == (k[4] + k[5] + k[6])&&sum == (k[7] + k[8] + k[9]))

13         {

14             if(sum1 == k[2]+k[5]+k[8]&&sum1 == k[3]+k[6]+k[9])

15                 z ++;

16             else

17                 return;

18         }

19         return ;

20     }

21     if(x > 7)

22     {

23         sum = k[1] + k[2] + k[3];

24         if(sum != (k[4] + k[5] + k[6]))

25         return ;

26     }

27     if(x == 9)

28     {

29         sum1 = k[1] + k[4] + k[7];

30         if(sum1 != k[2]+k[5]+k[8])

31         return ;

32     }

33     j = 1;

34     for(i = 1; i <= 9; i ++)

35     {

36         w = 1;

37         for(a = 1;a <= j-1;a ++)

38         {

39             if(q[a] == p[i])

40             {

41                 w = 0;

42                 break;

43             }

44         }

45         if(!o[i]&&w)

46         {

47             q[j] = p[i];

48             j ++;

49             k[x] = p[i];

50             o[i] = 1;

51             dfs(x+1);

52             o[i] = 0;

53         }

54     }

55 }

56 int main()

57 {

58     int i,t,num = 0;

59     scanf("%d",&t);

60     while(t--)

61     {

62         z = 0;

63         num ++;

64         memset(o,0,sizeof(o));

65         memset(k,0,sizeof(k));

66         for(i = 1; i <= 9; i ++)

67             scanf("%d",&p[i]);

68         dfs(1);

69         printf("Case %d: ",num);

70         printf("%d
",z); 71 } 72 return 0; 73 }