题目大意:
给出两个 $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; }
|