|
|
Posted on 2009-10-14 16:44 Hero 閱讀(251) 評論(0) 編輯 收藏 引用 所屬分類: 代碼如詩－－ACM
1 /*
2 TASK: wissqu
3 LANG: C++
4
5 Compiling
6 Compile: OK
7
8 Executing
9 Test 1: TEST OK [3.305 secs, 2808 KB]
10
11 All tests OK.
12 */
13 #include <stdio.h>
14 #include <string.h>
15
16 const int size = 1000 ;
17
18 char instr[100] ;
19 int data[6][6] ;
20 int flag[6][6] ;
21 int cownum[10] ;
22 int restemp[4][20] ;
23 int result[4][20] ;
24 int resnum ;
25
26 void input()
27 {
28 memset( data, 0, sizeof(data) ) ;
29 memset( cownum, 0, sizeof(cownum) ) ;
30
31 for( int i=1; i<=4; i++ )
32 {
33 scanf( "%s", &instr ) ;
34 for( int j=0; j<4; j++ )
35 {
36 data[i][j+1] = instr[j] - 'A' + 1 ;
37 cownum[data[i][j+1]]++ ;
38 }
39 }
40
41 cownum[3]-- ; cownum[4]++ ;
42 }
43
44 bool checkposi( int cowtype, int row, int col )
45 {
46 if( row<1 || row >4 || col<1 || col>4 ) return false ;
47 if( flag[row][col] ) return false ;
48
49 if( cowtype == data[row][col] ) return false ;
50 if( cowtype == data[row][col-1] ) return false ;
51 if( cowtype == data[row][col+1] ) return false ;
52
53 if( cowtype == data[row-1][col] ) return false ;
54 if( cowtype == data[row-1][col-1] ) return false ;
55 if( cowtype == data[row-1][col+1] ) return false ;
56
57 if( cowtype == data[row+1][col] ) return false ;
58 if( cowtype == data[row+1][col-1] ) return false ;
59 if( cowtype == data[row+1][col+1] ) return false ;
60
61 return true ;
62 }
63
64 void frescpy()
65 {
66 for( int i=0; i<=2; i++ )
67 {
68 for( int j=0; j<=16; j++ )
69 {
70 result[i][j] = restemp[i][j] ;
71 }
72 }
73 }
74 void fresult()
75 {
76 resnum = resnum + 1 ;
77 if( resnum == 1 ) memcpy( result, restemp, sizeof(result) ) ;
78
79 for( int i=0; i<=2; i++ )
80 {
81 for( int j=0; j<=15; j++ )
82 {
83 if( restemp[i][j] < result[i][j] )
84 {
85 //memcpy( result, restemp, sizeof(result) ) ;
86 return ;
87 }
88 }
89 }
90 }
91 void DFS( int cowtype, int row, int col, int step )
92 {
93 //printf( "step == %d tpye = %d row=%d col=%d\n", step, cowtype, row, col ) ;
94
95 if( row<1 || row >4 || col<1 || col>4 ) return ;
96 if( step > 15 ) return ;
97 if( flag[row][col] ) return ;
98 if( cownum[cowtype]<=0 ) return ;
99 if( !checkposi( cowtype, row, col ) ) return ;
100
101 int temp = data[row][col] ;
102 data[row][col] = cowtype ;
103 flag[row][col] = 1 ;
104 cownum[cowtype]-- ;
105
106 restemp[0][step] = cowtype ;
107 restemp[1][step] = row ;
108 restemp[2][step] = col ;
109
110 //if( step >=13 )
111 //printf( "step == %d tpye = %d row=%d col=%d\n", step, cowtype, row, col ) ;
112 if( step == 15 )
113 {
114 fresult() ;
115 }
116 else
117 {
118 for( int type=1; type<=5; type++ )
119 {
120 if( cownum[type] <= 0 ) continue ;
121 for( int r=1; r<=4; r++ )
122 {
123 for( int c=1; c<=4; c++ )
124 {
125 if( flag[r][c] ) continue ;
126 //for( int type=1; type<=5; type++ )
127 {
128 //if( cownum[type] <= 0 ) continue ;
129 DFS( type, r, c, step+1 ) ;
130 }
131 }
132 }
133 }
134 }
135
136 data[row][col] = temp ;
137 flag[row][col] = 0 ;
138 cownum[cowtype]++ ;
139 }
140
141 void solve()
142 {
143 resnum = 0 ;
144 memset( flag, 0, sizeof(flag) ) ;
145
146 for( int i=0; i<=2; i++ ) for( int j=0; j<=16; j++ ) result[i][j] = 9 ;
147
148 for( int r=1; r<=4; r++ )
149 {
150 for( int c=1; c<=4; c++ )
151 {
152 DFS( 4, r, c, 0 ) ;
153 }
154 }
155 }
156
157 void output()
158 {
159 for( int i=0; i<=15; i++ )
160 {
161 printf( "%c %d %d\n", result[0][i]+'A'-1, result[1][i], result[2][i] ) ;
162 }
163 printf( "%d\n", resnum ) ;
164 }
165
166 int main()
167 {
168 freopen( "wissqu.in", "r", stdin ) ;
169 freopen( "wissqu.out","w",stdout ) ;
170
171 input() ;
172
173 solve() ;
174
175 output() ;
176
177 return 0 ;
178 }
179
180
|