Posted on 2009-03-12 17:14
Hero 閱讀(155)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 const int size = 30 ;
6 int flag[size][size] ;
7
8 int inn ;
9 int count ;
10
11 bool test_line( int r, int c )
12 {
13 for( int i=1; i<=r; i++ )
14 {
15 if( 0 != flag[i][c] ) return false ;
16 }
17
18 return true ;
19 }
20
21 bool test_diag( int r, int c )
22 {
23 for( int i=1; i<=r; i++ )
24 {
25 if( 0 != flag[i][i+c-r] ) return false ;
26 if( 0 != flag[i][r+c-i] ) return false ;
27 }
28
29 return true ;
30 }
31
32 void DFS( int x, int y )
33 {
34 if( !(x>=1&&x<=inn&&y>=1&&y<=inn) ) return ;
35 if( !test_line( x, y ) ) return ;
36 if( !test_diag( x, y ) ) return ;
37
38 flag[x][y] = 1 ;
39 if( inn == x )
40 {
41 count ++ ;
42 }
43 else
44 {
45 for( int i=1; i<=inn; i++ ) DFS( x+1, i ) ;
46 }
47 flag[x][y] = 0 ;
48 }
49
50 int main()
51 {
52 while( scanf( "%d", &inn ) != EOF )
53 {
54 if( 0 == inn )
55 {
56 while( 1 ) ;
57 printf( "1\n" ) ; continue ;
58 }
59
60 memset( flag, 0, sizeof(flag) ) ;
61 count = 0 ;
62
63 for( int i=1; i<=inn; i++ )
64 {
65 //flag[1][i] = 1 ;
66 DFS( 1, i ) ;
67 //flag[1][i] = 0 ;
68 }
69
70 printf( "%d\n", count ) ;
71 }
72
73 return 0 ;
74 }