金币陈列问题 | 李博的博客
0%

金币陈列问题

题目大意:

给出两个 $m(n \leq 100)$ 行 $n(n \leq 100)$ 列的01矩阵分别为 $coin1[][]$ 和 $coin2[][]$ ,请问是否能通过两种操作使得 $coin1$ 变成 $coin2$ ,并计算出最少操作次数。

操作1:行变换 —— 01翻转
操作2:列变换 —— 交换两列

起初我的错误思路是:

  1. 先判断每一行,如果 1 的个数即不相同也不互补就是无解,互补就翻转
  2. 然后判断每一列,贪心计算最少交换次数,无法交换后和目标阵列相同就是无解

然后就发现了一个 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;//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;//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;
}
如果对您有帮助,请我喝杯奶茶?