bingo
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  0 随笔 :: 4 文章 :: 1 评论 :: 0 Trackbacks
金币阵列问题

 

  1//金币阵列问题，待改进。。。
  2
  3#include <stdio.h> 
  4#include <memory.h> 
  5
  6int ma[100][101], mb[100][101], mc[100][101]; 
  7int steps, tempsteps; 
  8int m, n; 
  9FILE *input, *output; 
 10
 11int input_matrix(int [][]); 
 12int row_overturn(int [][], int); 
 13int row_exchange(int [][], int, int); 
 14int row_match(int [][], int [][], int); 
 15int col_match(int, int, int, int); 
 16int col_exchange(int, int); 
 17int evaluate(int, int); 
 18int matrix_copy(int [][], int [][], int, int); 
 19
 20int row_match(int mx[][101], int my[][101], int i) 
 21{ 
 22    int j, count = 0; 
 23    for (j = 1; j <= n; ++j) 
 24        if (mx[i][j] != my[i][j]) 
 25            ++count; 
 26    if (count == n) 
 27        return 1; 
 28    else if(!count) 
 29        return 0; 
 30    else 
 31        return -1; 
 32} 
 33
 34int input_matrix(int mx[][101]) 
 35{ 
 36    int i, j, count1; 
 37    int tag = 0; 
 38    for (i = 0; i < m; ++i) 
 39    { 
 40        count1 = 0; 
 41        for (j = 1; j <= n; ++j) 
 42        { 
 43            fscanf(input, "%d", &mx[i][j]); 
 44            if (mx[i][j]) 
 45                ++count1; 
 46        } 
 47
 48        if (count1 * 2 != n) 
 49        { 
 50            mx[i][0] = count1; 
 51            if (i != tag) 
 52                row_exchange(mx, i, tag); 
 53            ++tag; 
 54        } 
 55        else 
 56            mx[i][0] = -1; 
 57    } 
 58
 59    return tag; 
 60} 
 61
 62int row_overturn(int mx[][101], int thisrow) 
 63{ 
 64    int j; 
 65
 66    for (j = 1; j <= n; j++) 
 67        mx[thisrow][j] = mx[thisrow][j] ^ 1; 
 68    if (mx[thisrow][0] >= 0) 
 69        mx[thisrow][0] = n - mx[thisrow][0]; 
 70
 71    ++steps; 
 72
 73    return 0; 
 74} 
 75
 76int row_exchange(int mx[][101], int row1, int row2) 
 77{ 
 78    int j, temp; 
 79    for (j = 0; j <= n; ++j) 
 80    { 
 81        temp = mx[row1][j]; 
 82        mx[row1][j] = mx[row2][j]; 
 83        mx[row2][j] = temp; 
 84    } 
 85
 86    return 0; 
 87} 
 88
 89int col_match(int x, int y, int fromrow, int torow) 
 90{ 
 91    int i; 
 92    for (i = fromrow; i < torow; ++i) 
 93        if (ma[i][x] != mb[i][y]) 
 94            return 0; 
 95
 96    return 1; 
 97} 
 98
 99int col_exchange(int col1, int col2) 
100{ 
101    int i, temp; 
102    for (i = 0; i < m; ++i) 
103    { 
104        temp = ma[i][col1]; 
105        ma[i][col1] = ma[i][col2]; 
106        ma[i][col2] = temp; 
107    } 
108    ++steps; 
109
110    return 0; 
111} 
112
113int matrix_copy(int mx[][101], int my[][101], int rowbound, int colbound) 
114{ 
115    int i, j; 
116    for (i = 0; i < rowbound; ++i) 
117        for (j = 0; j <= colbound; ++j) 
118            mx[i][j] = my[i][j]; 
119
120    return 0; 
121} 
122
123int evaluate(int fromrow, int col) 
124{ 
125    int i, degree = 0; 
126    for (i = fromrow; i < m; ++i) 
127        if (ma[i][col] == mb[i][1]) 
128            ++degree; 
129
130    return degree; 
131} 
132
133int main() 
134{ 
135    int c, i, j, j1, from, able, tag1, tag2, step, bestcol = 1, temp; 
136    int order[101], count[101]; 
137
138    output = fopen("output.txt", "w"); 
139    input = fopen("input.txt", "r"); 
140
141    fscanf(input, "%d", &c); 
142
143    for ( ; c; --c) 
144    { 
145        fscanf(input, "%d %d", &m, &n); 
146        tag1 = input_matrix(ma); 
147        tag2 = input_matrix(mb); 
148
149        if (tag1 != tag2) 
150        { 
151            fprintf(output, "-1\n"); 
152            continue; 
153        } 
154        else 
155        { 
156            //将 1,0个数相等的行往下沉 
157            for (i = 0, able = 1; i < tag1; ++i) 
158            { 
159                if (ma[i][0] == mb[i][0]) 
160                    continue; 
161                else if (ma[i][0] == n - mb[i][0]) 
162                    row_overturn(ma, i); 
163                else 
164                { 
165                    fprintf(output, "-1\n"); 
166                    able = 0; 
167                    goto loop1; 
168                } 
169            } 
170            loop1: 
171                if (!able) 
172                    continue; 
173
174            //排列 1,0个数相等的行之上的所有列 
175            for (j = 1, from = 1; j <= n; ++j) 
176            { 
177                for (j1 = from, able = 0; j1 <= n; ++j1) 
178                    if (col_match(j1, j, 0, tag1)) 
179                    { 
180                        if (j1 != j) 
181                            col_exchange(j1, j); 
182                        ++from; 
183                        able = 1; 
184                        break; 
185                    } 
186
187                if (!able) 
188                { 
189                    fprintf(output, "-1\n"); 
190                    goto loop2; 
191                } 
192            } 
193            loop2: 
194                if (!able) 
195                       continue; 
196
197            if (tag1 == m) 
198            { 
199                fprintf(output, "%d\n", steps); 
200                continue; 
201            } 
202
203            //处理剩下 0,1个数相等的行 
204            for (j = 1; j <= n; ++j) 
205            { 
206                order[j] = j; 
207                count[j] = evaluate(tag1, j); 
208            } 
209
210            for (i = 1; i < n; ++i) 
211                for (j = 1; j <= n - i; ++j) 
212                    if (count[j] < count[j + 1]) 
213                    { 
214                        temp = order[j]; 
215                        order[j] = order[j + 1]; 
216                        order[j + 1] = temp; 
217                    } 
218
219            /* 
220            for (j = 1; j <= n; ++j) 
221                printf("%-2d ", count[order[j]]); 
222
223            printf("\n"); 
224
225            for (j = 1; j <= n; ++j) 
226                printf("%-2d ", order[j]); 
227
228            printf("\n"); 
229            */ 
230
231            for (i = tag1, able = 1, tempsteps = 0; i < m; ++i) 
232            { 
233                step = row_match(ma, mb, i); 
234                if (step < 0) 
235                { 
236                    able = 0; 
237                    break; 
238                } 
239                else if (step) 
240                    tempsteps += step; 
241                else 
242                    ; 
243            } 
244
245            if (able) 
246            { 
247                steps += tempsteps; 
248                fprintf(output, "%d\n", steps); 
249                continue; 
250            } 
251
252            tempsteps = steps; 
253
254            //找到和目标第一列的最优匹配 
255            loop3: 
256            steps = tempsteps; 
257            for (j1 = bestcol, j = order[j1], able = 0; j1 <= n; ++j1) 
258                if (col_match(j, 1, 0, tag1)) 
259                { 
260                    able = 1; 
261                    matrix_copy(mc, ma, m, n); 
262                     bestcol = j1 + 1; 
263                    for (i = tag1; i < m; ++i) 
264                        if (ma[i][j] != mb[i][1]) 
265                               row_overturn(ma, i); 
266                    if (j != 1) 
267                        col_exchange(j, 1); 
268                    break; 
269                } 
270
271            if (!able) 
272            { 
273                fprintf(output, "-1\n"); 
274                continue; 
275            } 
276
277               for (j = 2, from = 2; j <= n; ++j) 
278            { 
279                for (j1 = from, able = 0; j1 <= n; ++j1) 
280                { 
281                    if (col_match(j1, j, 0, m)) 
282                    { 
283                        if (j1 != j) 
284                            col_exchange(j, j1); 
285                        able = 1; 
286                        ++from; 
287                        break; 
288                    } 
289                } 
290                if (!able) 
291                    break; 
292            } 
293
294            //找到 
295            if (able) 
296            { 
297                for (i = 0; i < m; ++i) 
298                { 
299                    for (j = 0; j <= n; ++j) 
300                        printf("%-2d ", ma[i][j]); 
301                    printf("\n"); 
302                } 
303                printf("steps: %d\n", steps); 
304                continue; 
305            } 
306            else if (!able && bestcol == n - 1) 
307            { 
308                fprintf(output, "-1\n"); 
309                continue; 
310            } 
311            else 
312            { 
313                for (i = 0; i < m; ++i) 
314                { 
315                    for (j = 0; j <= n; ++j) 
316                        printf("%-2d ", mc[i][j]); 
317                    printf("\n"); 
318                } 
319                matrix_copy(ma, mc, m, n); 
320                goto loop3; 
321            } 
322        } 
323        steps = 0; 
324    } 
325
326    /* 
327    for (i = 0; i < m; ++i) 
328    { 
329        for (j = 0; j <= n; ++j) 
330            printf("%-2d ", ma[i][j]); 
331        printf("\n"); 
332    } 
333
334    printf("\n"); 
335
336    for (i = 0; i < m; ++i) 
337    { 
338        for (j = 0; j <= n; ++j) 
339            printf("%-2d ", mb[i][j]); 
340        printf("\n"); 
341    } 
342    */ 
343
344    return 0; 
345}
346
posted on 2008-12-24 15:26 bingo 阅读(553) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理