fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 105;
  5. int n, a[N][N], b[N][N];
  6.  
  7. typedef vector<pair<int,int>> instructions;
  8. bool cmp(const instructions& a, const instructions& b) {
  9.     return a.size() < b.size();
  10. }
  11.  
  12. int c[N][N];
  13. bitset<N> column_c[N], column_b[N];
  14. int id_b[N], id_c[N];
  15. vector<int> group_c[N], group_b[N]; 
  16. bool solve(instructions& res) {
  17.     //transform table c to table b
  18.     res.size();
  19.     for (int j = 1; j <= n; j++) {
  20.         column_c[j].reset();
  21.         column_b[j].reset();
  22.         for (int i = 1; i <= n; i++) 
  23.             column_c[j].set(i, c[i][j]),
  24.             column_b[j].set(i, b[i][j]);
  25.     }
  26.     for (int i = 1; i <= n; i++) {
  27.         group_b[i].clear();
  28.         group_c[i].clear();
  29.         group_b[i].push_back(i);
  30.         group_c[i].push_back(i);
  31.         id_b[i] = i, id_c[i] = i;
  32.     }
  33.     for (int i = 1; i <= n; i++) {
  34.         if (id_b[i] < i) continue;
  35.         for (int j = i+1; j <= n; j++)
  36.             if (column_b[j] == column_b[i])
  37.                 id_b[j] = i, group_b[i].push_back(j);
  38.     }
  39.     for (int i = 1; i <= n; i++) {
  40.         if (id_c[i] < i) continue;
  41.         for (int j = i+1; j <= n; j++)
  42.             if (column_c[j] == column_c[i])
  43.                 id_c[j] = i, group_c[i].push_back(j);
  44.     }
  45.     int perm[N];
  46.     for (int i = 1; i <= n; i++) {
  47.         if (id_c[i] < i) continue;
  48.         bool found = false;
  49.         for (int j = 1; j <= n; j++)
  50.             if (id_b[j] == j and column_c[i] == column_b[j]) {
  51.                 found = true;
  52.                 if (group_c[i].size() != group_b[j].size()) return false;
  53.                 for (int k = 0; k < (int) group_c[i].size(); k++)
  54.                     perm[group_c[i][k]] = group_b[j][k];
  55.             }
  56.         if (!found) return false;
  57.     }
  58.     for (int i = 1; i <= n; i++) {
  59.         int j = -1;
  60.         for (int k = i; k <= n; k++)
  61.             if (perm[k] == i) { j = k; break; }
  62.         for (int k = j-1; k >= i; k--) {
  63.             swap(perm[k], perm[k+1]);
  64.             res.emplace_back(1,k);
  65.         }
  66.     }
  67.     return true;
  68. }
  69.  
  70. void subtask4() {
  71.     vector<instructions> solutions;
  72.     for (int col_c : {n,n-1}) {
  73.         for (int col_b = 1; col_b <= n; col_b++) {
  74.             instructions cur;
  75.             int cnt_diff = 0, diff = 0, pos = 0;
  76.             for (int i = 1; i <= n; i++) {
  77.                 bool flip = a[i][col_c] != b[i][col_b];
  78.                 if (flip) cur.emplace_back(2,i);
  79.                 for (int j = 1; j <= n; j++)
  80.                     c[i][j] = flip ? 1-a[i][j] : a[i][j];
  81.                 int cnt_c = count(c[i]+1, c[i]+1+n, 1);
  82.                 int cnt_b = count(b[i]+1, b[i]+1+n, 1);
  83.                 if (cnt_c != cnt_b) pos = i;
  84.                 cnt_diff += abs(cnt_b - cnt_c);
  85.                 diff += cnt_c - cnt_b;
  86.             }
  87.             if (cnt_diff > 1) continue;
  88.             if (cnt_diff == 1) {
  89.                 int bit = (diff > 0) ? 1 : 0;
  90.                 for (int j = 1; j <= n; j++)
  91.                     if (j != col_c and c[pos][j] == bit) {
  92.                         instructions nxt = cur;
  93.                         c[pos][j] ^= 1;
  94.                         if (solve(nxt)) solutions.push_back(nxt);
  95.                         c[pos][j] ^= 1;
  96.                     }
  97.             } else 
  98.             if (solve(cur)) solutions.push_back(cur);
  99.         }
  100.     }   
  101.     if (solutions.empty())
  102.         { puts("-1"); return ; }
  103.     auto ans = *min_element(begin(solutions), end(solutions), cmp);
  104.     printf("%d\n", (int) ans.size());
  105.     for (auto cmd : ans)
  106.         printf("%d %d\n", cmd.first, cmd.second);
  107. }
  108.  
  109. int main() 
  110. {
  111.     #define task "board"
  112.     if (fopen(task".inp", "r")) {
  113.         freopen(task".inp", "r", stdin);
  114.         freopen(task".out", "w", stdout);
  115.     }
  116.     scanf("%d", &n);
  117.     for (int i = 1; i <= n; i++)
  118.         for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
  119.     for (int i = 1; i <= n; i++)
  120.         for (int j = 1; j <= n; j++) scanf("%d", &b[i][j]);
  121.     subtask4();
  122.  
  123. }
  124.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/KkkyXE
language:
C++14 (gcc 8.3)
created:
7 days 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!