bingo
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
0 随笔 :: 4 文章 :: 1 评论 :: 0 Trackbacks
<
2024年8月
>
日
一
二
三
四
五
六
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
文章档案
2008年12月 (2)
2008年7月 (2)
搜索
最新评论
1. re: POJ 1007
写的不错啊。
--Brian
金币阵列问题
1
//
金币阵列问题,待改进。。。
2
3
#include
<
stdio.h
>
4
#include
<
memory.h
>
5
6
int
ma[
100
][
101
], mb[
100
][
101
], mc[
100
][
101
];
7
int
steps, tempsteps;
8
int
m, n;
9
FILE
*
input,
*
output;
10
11
int
input_matrix(
int
[][]);
12
int
row_overturn(
int
[][],
int
);
13
int
row_exchange(
int
[][],
int
,
int
);
14
int
row_match(
int
[][],
int
[][],
int
);
15
int
col_match(
int
,
int
,
int
,
int
);
16
int
col_exchange(
int
,
int
);
17
int
evaluate(
int
,
int
);
18
int
matrix_copy(
int
[][],
int
[][],
int
,
int
);
19
20
int
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
34
int
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
62
int
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
76
int
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
89
int
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
99
int
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
113
int
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
123
int
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
133
int
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
阅读(557)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © bingo