题目大意：
给出两个 $m(n \leq 100)$ 行 $n(n \leq 100)$ 列的01矩阵分别为 $coin1[][]$ 和 $coin2[][]$ ，请问是否能通过两种操作使得 $coin1$ 变成 $coin2$ ，并计算出最少操作次数。
操作1：行变换 —— 01翻转
操作2：列变换 —— 交换两列
起初我的错误思路是：
- 先判断每一行，如果 1 的个数即不相同也不互补就是无解，互补就翻转
- 然后判断每一列，贪心计算最少交换次数，无法交换后和目标阵列相同就是无解
然后就发现了一个 bug ，如果 n 为偶数并且 1 的个数既相同，那么就是既可以换也可以不换。这样复杂度就由原来的 $O(mn)$ 上升为 $O(mn2^m)$ ，显然不行。
如：
1
2
3
4
5
| 2 4
0 1 1 0
0 1 1 1
0 1 1 0
1 0 1 1
|
第一行不交换就是无解，换了就有解。
正确思路：
可以枚举初始状态矩阵每一列变成目标状态第一列的情况，取结果的最小值。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int coin1[maxn][maxn], coin2[maxn][maxn], temp[maxn][maxn];
int n, m, k;
int cnt;
void cp(int a[maxn][maxn], int b[maxn][maxn]){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
a[i][j] = b[i][j];
}
}
}
void changeColumn(int x, int y){
if(x == y) return ;
for(int i=0; i<n; i++) swap(temp[i][x], temp[i][y]);
cnt++;
}
void changeRow(int x){
for(int i=0; i<m; i++) temp[x][i]^=1;
cnt++;
}
bool same(int x, int y){
for(int i=0; i<n; i++){
if(coin2[i][x] != temp[i][y]) return false;
}
return true;
}
int main(){
cin >> k;
while(k--){
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> coin1[i][j];
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> coin2[i][j];
}
}
int ans = INF;
for(int cur=0; cur<m; cur++){
cp(temp, coin1); cnt = 0; changeColumn(0, cur);
for(int i=0; i<n; i++){
if(temp[i][0] != coin2[i][0]) changeRow(i);
}
bool found;
for(int i=0; i<m; i++){
found = false;
if(same(i, i)){
found = true;
continue;
}
for(int j=i+1; j<m; j++){
if(same(i, j)){
if(same(j, j)) continue;
changeColumn(i, j);
found = true;
break;
}
}
if(!found) break;
}
if(found && cnt<ans) ans = cnt;
}
cout << (ans == INF ? -1 : ans) << endl;
}
return 0;
}
|
henu计算机算法设计与分析ac代码：
某老师神奇般的放了三个空的文件作为测试数据，就是这么坑！
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int coin1[maxn][maxn], coin2[maxn][maxn], temp[maxn][maxn];
int n, m;
int cnt;
void cp(int a[maxn][maxn], int b[maxn][maxn]){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
a[i][j] = b[i][j];
}
}
}
void changeColumn(int x, int y){
if(x == y) return ;
for(int i=0; i<n; i++) swap(temp[i][x], temp[i][y]);
cnt++;
}
void changeRow(int x){
for(int i=0; i<m; i++) temp[x][i]^=1;
cnt++;
}
bool same(int x, int y){
for(int i=0; i<n; i++){
if(coin2[i][x] != temp[i][y]) return false;
}
return true;
}
int main(){
string str;
if(cin >> str){
n = str[0] - '0';
m = str[2] - '0';
for(int i=0; i<n; i++){
cin >> str;
for(int j=0; j<m; j++){
coin1[i][j] = str[j] - '0';
}
}
for(int i=0; i<n; i++){
cin >> str;
for(int j=0; j<m; j++){
coin2[i][j] = str[j] - '0';
}
}
int ans = INF;
for(int cur=0; cur<m; cur++){
cp(temp, coin1); cnt = 0; changeColumn(0, cur);
for(int i=0; i<n; i++){
if(temp[i][0] != coin2[i][0]) changeRow(i);
}
bool found;
for(int i=0; i<m; i++){
found = false;
if(same(i, i)){
found = true;
continue;
}
for(int j=i+1; j<m; j++){
if(same(i, j)){
if(same(j, j)) continue;
changeColumn(i, j);
found = true;
break;
}
}
if(!found) break;
}
if(found && cnt<ans) ans = cnt;
}
cout << (ans == INF ? -1 : ans);
}
return 0;
}
|