|
|
Posted on 2008-10-05 23:04 Hero 閱讀(129) 評論(0) 編輯 收藏 引用 所屬分類: 代碼如詩－－ACM
1 /*
2 ID: wangzha4
3 LANG: C++
4 TASK: starry
5 */
6 /*
7 Executing
8 Test 1: TEST OK [0.000 secs, 3136 KB]
9 Test 2: TEST OK [0.011 secs, 3140 KB]
10 Test 3: TEST OK [0.022 secs, 3140 KB]
11 Test 4: TEST OK [0.011 secs, 3140 KB]
12 Test 5: TEST OK [0.000 secs, 3136 KB]
13 */
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18
19 const int INF = 999999 ;
20 const int size = 110 ;
21 char data[size][size] ;
22 int flag[size][size] ;
23 int cflag ;
24
25 char tcluster[size][size] ; int trow, tcol ;
26 char A[size][size], B[size][size] ;
27 char cluster[27][size][size] ;
28 int lenwid[30][2] ;
29
30 char flagtostr[3000] ; char str ;
31
32 int len, wid ;
33 int num ;
34
35 int next[9][2] ;
36
37 int row, col ;
38 int snrow, enrow ;
39 int sncol, encol ;
40
41 int fmax( int a, int b )
42 {
43 return a > b ? a : b ;
44 }
45 int fmin( int a, int b )
46 {
47 return a < b ? a : b ;
48 }
49
50 void input()
51 {
52 memset( flag, 0, sizeof(flag) ) ; cflag = 1 ; str = 'a' ;
53 memset( lenwid, 0, sizeof(lenwid) ) ; flagtostr[0] = '0' ;
54
55 for( int i=0; i<row; i++ ) scanf( "%s", data[i] ) ;
56
57 next[1][0] = -1 ; next[1][1] = -1 ;
58 next[2][0] = -1 ; next[2][1] = 0 ;
59 next[3][0] = -1 ; next[3][1] = +1 ;
60
61 next[4][0] = 0 ; next[4][1] = -1 ;
62 next[5][0] = 0 ; next[5][1] = +1 ;
63
64 next[6][0] = +1 ; next[6][1] = -1 ;
65 next[7][0] = +1 ; next[7][1] = 0 ;
66 next[8][0] = +1 ; next[8][1] = +1 ;
67 }
68
69 bool in( int r, int c )
70 {
71 if( r>=0&&r<row&&c>=0&&c<col ) return true ;
72
73 return false ;
74 }
75 void DFS( int r, int c )
76 {
77 snrow = fmin( snrow, r ) ; sncol = fmin( sncol, c ) ;
78 enrow = fmax( enrow, r ) ; encol = fmax( encol, c ) ;
79 flag[r][c] = cflag ; data[r][c] = '0' ;
80
81 for( int i=1; i<=8; i++ )
82 {
83 int nextr = r+next[i][0] ; int nextc = c+next[i][1] ;
84 if( in( nextr, nextc ) && 0==flag[nextr][nextc] && data[nextr][nextc]!='0' )
85 DFS( nextr, nextc ) ;
86 }
87 }
88
89 bool compare( char C[][size], int len, int wid, int i )
90 {
91 for( int r=0; r<=len; r++ ) for( int c=0; c<=wid; c++ )
92 {
93 if( cluster[i][r][c] != C[r][c] ) return false ;
94 }
95 return true ;
96 }
97
98 void turn90( char sour[size][size], char dest[size][size], int row, int col )
99 {
100 //memset( dest, 0, sizeof(dest) ) ;
101 for( int i=0; i<size; i++ ) for( int j=0; j<size; j++ ) dest[i][j] = 0 ;
102 for( int r=0; r<=row; r++ ) for( int c=0; c<=col; c++ )
103 dest[c][row-r] = sour[r][c] ;
104 }
105
106 void turnupdn( char sour[size][size], int row, int col )
107 {
108 char dest[size][size] ; memset( dest, 0, sizeof(dest) ) ;
109 for( int r=0; r<=row; r++ ) for( int c=0; c<=col; c++ )
110 dest[row-r][c] = sour[r][c] ;
111
112 //memcpy( sour, dest, sizeof(dest) ) ;
113 for( int r=0; r<size; r++ ) for( int c=0; c<size; c++ )
114 sour[r][c] = dest[r][c] ;
115 }
116
117 int find( int len, int wid )
118 {
119 for( int i=0; i<=1; i++ )
120 {
121 if( 0 == i )
122 {
123 memset( A, 0, sizeof(A) ) ;
124 for( int r=snrow; r<=enrow; r++ ) for( int c=sncol; c<=encol; c++ )
125 {
126 if( cflag == flag[r][c] ) A[r-snrow][c-sncol] = '1' ;
127 }
128 }
129 else
130 {
131 turn90( B, A, wid, len ) ; turnupdn( A, len, wid ) ;
132 }
133 for( int i=1; i<=num; i++ )
134 {
135 if( lenwid[i][0]!=len || lenwid[i][1]!=wid ) continue ;
136 else
137 if( compare( A, len, wid, i ) ) return i ;
138 }
139 turn90( A, B, len, wid ) ;
140 for( int i=1; i<=num; i++ )
141 {
142 if( lenwid[i][0]!=wid || lenwid[i][1]!= len ) continue ;
143 else
144 if( compare( B, wid, len, i ) ) return i ;
145 }
146 turn90( B, A, wid, len ) ;
147 for( int i=1; i<=num; i++ )
148 {
149 if( lenwid[i][0]!=len || lenwid[i][1]!=wid ) continue ;
150 else
151 if( compare( A, len, wid, i ) ) return i ;
152 }
153 turn90( A, B, len, wid ) ;
154 for( int i=1; i<=num; i++ )
155 {
156 if( lenwid[i][0]!=wid || lenwid[i][1]!= len ) continue ;
157 else
158 if( compare( B, wid, len, i ) ) return i ;
159 }
160 }
161
162 return 0 ;
163 }
164
165 void process()
166 {
167 memset( cluster, 0, sizeof(cluster) ) ; num = 0 ;
168
169 for( int r=0; r<row; r++ )
170 {
171 for( int c=0; c<col; c++ )
172 {
173 if( 0==flag[r][c] && data[r][c]!='0' )
174 {
175 snrow = r ; enrow = r ; sncol = INF ; encol = 0 ; DFS( r, c ) ;
176
177 len = enrow - snrow ; wid = encol - sncol ;
178
179 int findnum = find( len, wid ) ;
180
181 if( findnum != 0 )
182 {
183 flagtostr[cflag++] = 'a'-1+findnum ;
184 }
185 else
186 {
187 num++ ; flagtostr[cflag] = str++ ;
188 for( int r=snrow; r<=enrow; r++ ) for( int c=sncol; c<=encol; c++ )
189 {
190 if( cflag == flag[r][c] ) cluster[num][r-snrow][c-sncol] = '1' ;
191 }
192
193 lenwid[num][0] = len ; lenwid[num][1] = wid ; cflag++ ;
194 }
195 }
196 }
197 }
198 }
199
200 void output()
201 {
202 /*
203 for( int i=0; i<row; i++ )
204 {
205 for( int j=0; j<col; j++ )
206 {
207 printf( "%-3d", flag[i][j] ) ;
208 }
209 printf( "\n" ) ;
210 }
211 printf( "**************************\n" ) ;
212 */
213 for( int i=0; i<row; i++ )
214 {
215 for( int j=0; j<col; j++ )
216 {
217 printf( "%c", flagtostr[flag[i][j]] ) ;
218 }
219 printf( "\n" ) ;
220 }
221 }
222
223 int main()
224 {
225 //freopen( "in.txt", "r", stdin ) ;
226 //freopen( "out.txt", "w", stdout ) ;
227 freopen( "starry.in", "r", stdin ) ;
228 freopen( "starry.out", "w", stdout ) ;
229
230 while( scanf( "%d %d", &col, &row )!= EOF )
231 {
232 input() ;
233
234 process() ;
235
236 output() ;
237 }
238
239 return 0 ;
240 }
|