fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. const int MAXN = 22;
  8. const int INF = 1e9;
  9.  
  10. int n;
  11. int original[MAXN][MAXN];  // 原始矩阵
  12. int temp[MAXN][MAXN];       // 临时矩阵，用于模拟翻转
  13. int flip[MAXN][MAXN];       // 记录是否主动翻转
  14.  
  15. // 判断是否应该翻转当前位置
  16. bool needFlip(int r, int c) {
  17.     // 检查当前位置上方格子的状态
  18.     // 如果上方格子是1，那么当前位置需要主动翻转
  19.     int cnt = temp[r-1][c];  // 上方格子的值
  20.  
  21.     // 加上周围主动翻转的影响
  22.     if (c > 1) cnt += flip[r-1][c-1];
  23.     if (c < n) cnt += flip[r-1][c+1];
  24.     if (r > 1) cnt += flip[r-2][c];
  25.  
  26.     // 奇数个翻转（包括被动翻转）会让值改变
  27.     return (cnt % 2 == 1);
  28. }
  29.  
  30. int solve() {
  31.     int minFlips = INF;
  32.  
  33.     // 枚举第一行的所有翻转情况（2^n种可能）
  34.     for (int mask = 0; mask < (1 << n); mask++) {
  35.         memset(flip, 0, sizeof(flip));
  36.  
  37.         // 复制原始矩阵到临时矩阵
  38.         for (int i = 1; i <= n; i++) {
  39.             for (int j = 1; j <= n; j++) {
  40.                 temp[i][j] = original[i][j];
  41.             }
  42.         }
  43.  
  44.         // 设置第一行的翻转
  45.         int flips = 0;
  46.         for (int j = 1; j <= n; j++) {
  47.             if (mask & (1 << (j-1))) {
  48.                 flip[1][j] = 1;
  49.                 flips++;
  50.  
  51.                 // 应用翻转：自身和四个邻居
  52.                 temp[1][j] ^= 1;
  53.                 if (j > 1) temp[1][j-1] ^= 1;
  54.                 if (j < n) temp[1][j+1] ^= 1;
  55.                 temp[2][j] ^= 1;
  56.             }
  57.         }
  58.  
  59.         // 根据上一行的状态决定当前行是否翻转
  60.         for (int i = 2; i <= n; i++) {
  61.             for (int j = 1; j <= n; j++) {
  62.                 // 如果上一行的当前位置是1，那么当前行对应位置需要翻转
  63.                 if (temp[i-1][j] == 1) {
  64.                     flip[i][j] = 1;
  65.                     flips++;
  66.  
  67.                     // 应用翻转
  68.                     temp[i][j] ^= 1;
  69.                     if (j > 1) temp[i][j-1] ^= 1;
  70.                     if (j < n) temp[i][j+1] ^= 1;
  71.                     temp[i+1][j] ^= 1;
  72.                 }
  73.             }
  74.         }
  75.  
  76.         // 检查最后一行是否全为0
  77.         bool allZero = true;
  78.         for (int j = 1; j <= n; j++) {
  79.             if (temp[n][j] == 1) {
  80.                 allZero = false;
  81.                 break;
  82.             }
  83.         }
  84.  
  85.         if (allZero) {
  86.             minFlips = min(minFlips, flips);
  87.         }
  88.     }
  89.  
  90.     return (minFlips == INF) ? -1 : minFlips;
  91. }
  92.  
  93. int main() {
  94.     cin >> n;
  95.  
  96.     // 读入矩阵
  97.     for (int i = 1; i <= n; i++) {
  98.         string s;
  99.         cin >> s;
  100.         for (int j = 1; j <= n; j++) {
  101.             original[i][j] = s[j-1] - '0';
  102.         }
  103.     }
  104.  
  105.     cout << solve() << endl;
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
1 1 1
1 1 1
1 1 1
stdout
copy 
1
https://ideone.com/4ro5Dc
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!