解説

問題文を 2 段階言い換えます．まず， $a$ と $b$ が 2 つあるのが大変なので 1 つにまとめます．

"""

$b _ {ij}$ が ? のときは， $c _ {ij} =$ ? で，そうでない時は， $c _ {ij} = a _ {ij} \oplus b _ {ij}$ となるグリッド $c$ を考えます．

このとき， $c$ の同じ行または同じ列の 2 つのセルを選んで，反転させる．( ? は ? のまま) $c$ から 1 が消えるために必要な操作回数が最小となるような操作の一例をあげよ．

"""

となります．1 を消す操作は主に 4 通りあって，上から順に得です．( 2 番目と 3 番目は同じ得レベル)

同じ行や列の 2 つの 1 を 1 手で 0 にする．
行や列を共有していない 2 つの 1 を 2 手で 0 にする．
? と同じ行や列の 1 つの 1 を 1 手で 0 にする．
? と行や列を共有していない 1 を 2 手で 0 にする．

3 番目と 4 番目の操作は ? が存在するときにのみ使用できます．

グリッドのまま考えるのは大変です．グリッドの，x 座標と，y 座標を頂点とし，1 の x 座標と y 座標に辺を貼った無向グラフ $G(V, E)$ を考えてみます．このとき，次のように問題文を言い換えられます．

"""

$(u, v _ {1}) \in V \times V, (u, v _ {2}) \in V \times V$ となる頂点組において，辺がある状態とない状態を反転させる．このとき， ? のところを除き， $G$ 上から辺がなくなるために必要な操作回数が最小となるような操作の一例をあげよ．

"""

と言い換えます．これでグラフの問題になり，消せる条件が頂点に注目するだけになり見通しが良くなりました．各連結成分に注目します．次の事実が言えます．

"""

1 番目の操作のみだけで，連結成分の辺の数が偶数なら全て消せて，辺の数が奇数なら，1つ残すのみにすることができる．

"""

1 番目の操作は 2 本ずつ辺を削除するので，偶数の場合は全部消すのが，奇数の場合は 1 つ残すよりも良くすることができないです．次に可能なことを具体的な操作を構築することで示します．

f:id:jupiro:20210412134956p:plain — 黄色が DFS 木の辺で，青色が後退辺

上の図のように，DFS 木を取って，葉のほうから，辺を削除することを考えます．

注目してる頂点につながっている辺が偶数本の場合は，1 番目の操作で全て削除することができます．奇数本の場合を考えます．奇数本の場合どのように操作しても，1 番目の操作のみでは 1 本残ります．どの辺を残すかを考えます．子に辺が残っている場合，葉から見ていることから，ここで削除しないと削除できないので，削除するのが得です．後退辺と親につながる辺は，どちらを残していても，あとで消すことができますが，親につながる辺を残すことで，もし辺が残っているなら，DFS 木上の辺のみとなることから，実装上が楽なのでおすすめです．この操作を全部葉から繰り返していくことで，連結成分の辺の数が，偶数の場合は全て削除でき，奇数の場合は辺を 1 つ残すのみにすることが可能ということがわかります．

グラフ全体の辺の数に注目します．

グラフ全体の辺の数が偶数の時．

1 番目の操作をすることで，1 本辺が残っている連結成分は偶数個です．これらは，2 番目の操作をすることで，全て削除できるので，グラフ全体の辺の数が偶数の時は求めることができました．

グラフ全体の辺の数が奇数の時．

? がないときは，どのように操作しても，2 つずつしか消せないので，1を全て消すことはできません．以下，? が存在する場合を考えます．3 番目の操作，または 4 番目の操作を (適切に) 1 度すれば，グラフ全体の辺の数が偶数の場合の話に帰着できます．3 番目の操作は 4 番目の操作より得であるので， 3 番目の操作を適用できる場合を考えます．連結成分の辺の数が偶数の連結成分には適用をするのは損です．連結成分の辺の数が偶数の連結成分は，操作 1 のみで全て削除することが可能だからです．よって，連結成分の辺の数が奇数の連結成分の辺に適用できるときは，1 度だけ 3 番目の操作を適用することで，グラフ全体の辺の数が偶数の時に帰着できます．3 番目の操作が適用できない時は， 4 番目の操作を適用し，グラフ全体の辺の数が偶数の時に帰着させて解くことができました．

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <array>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>
#include <chrono>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

namespace KKT89
{
  struct UnionFind
  {
    std::vector<int> par, edge;
    UnionFind(int n)
    {
        par.assign(n, -1);
        edge.assign(n, 0);
    }
    int root(int a)
    {
        if (par[a] < 0)
        {
            return a;
        }
        return par[a] = root(par[a]);
    }

    int size(int a)
    {
        return -par[root(a)];
    }
    bool connect(int a, int b)
    {
        a = root(a);
        b = root(b);
        edge[a] += 1;
        if (a == b)
        {
            return false;
        }
        if (size(a) < size(b))
        {
            std::swap(a, b);
        }
        edge[a] += edge[b];
        par[a] += par[b];
        par[b] = a;

        return true;
    }
    bool same(int a, int b)
    {
        return root(a) == root(b);
    }

    int get_edge(int a)
    {
      a = root(a);
      return edge[a];
    }
  };
}

void solve()
{
  int n, m, E; cin >> n >> m >> E;
  std::vector a(n, std::vector<int>(m));
  KKT89::UnionFind uf(n + m);
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < m; ++j)
    {
      char c; cin >> c;
      a[i][j] = c - '0';
    }
  }

  //?のあるとこ
  std::pair<int, int> question(-1, -1);
  std::vector<int> R(n, -1), C(m, -1);  
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < m; ++j)
    {
      char c; cin >> c;
      if(c == '?')
      {
        a[i][j] = -1;
        question = {i, j};
        R[i] = j;
        C[j] = i;
      }
      else
        a[i][j] ^= (c - '0');
    }
  }
  std::vector<std::vector<int>> g(n + m);
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < m; ++j)
    {
      if(a[i][j] == 1)
      {
        uf.connect(i, n + j);
        g[i].emplace_back(n + j);
        g[n + j].emplace_back(i);
      }
    }
  }
  std::vector<bool> used(n + m);
  std::vector<int> dep(n + m);
  std::vector<std::tuple<int, int, int>> res;
  auto dfs = [&](auto&& self, 
    const int cur, int pre, bool &f)->int
  {
    used[cur] = true;
    std::vector<int> v;
    for(const auto nxt : g[cur])
    {
      if(not used[nxt])
      {
        dep[nxt] = dep[cur] + 1;
        auto p = self(self, nxt, cur, f);
        if(p == 1)
        {
          v.emplace_back(nxt);
        }
      }
      else if(dep[nxt] < dep[cur])
      {
        if(nxt != pre)
          v.emplace_back(nxt);
      }
    }
    int ret = 0;

    int que = -1;
    if(cur >= n and C[cur - n] >= 0)
      que = C[cur - n];
    if(cur < n and R[cur] >= 0)
      que = R[cur] + n;
    bool usepre = false;
    if(f and que != -1 and (pre >= 0 or not v.empty()))
    {
      if(not v.empty())
      {
        res.emplace_back(cur, que, v.back());
        v.pop_back();
      }
      else
      {
        usepre = true;
        res.emplace_back(cur, pre, que);
      }
      f = false;
    }
    for (int i = 0; i + 1 < (int)v.size(); i += 2)
    {
      res.emplace_back(cur, v[i], v[i + 1]);
    }
    if((int)v.size() % 2 == 1)
    {
      if(pre == -1 or usepre)
      {
        ret = 1;
      }
      else
      {
        res.emplace_back(cur, pre, v.back());
      }
    }
    else
    {
      if(pre >= 0 and not usepre)
        ret = 1;
    }
    if(pre == -1 and ret == 1)
    {
      return v.back();
    }
    return ret;
  };
  int cnt = 0;
  for (int i = 0; i < n + m; ++i)
  {
    if(uf.root(i) == i)
    {
      if(uf.get_edge(i) % 2 == 1)
      {
        cnt += 1;
      }
    }
  }
  bool f = cnt % 2;
  std::vector<std::pair<int, int>> vp;
  for (int i = 0; i < n + m; ++i)
  {
    if(used[i])
      continue;
    int r = 0;
    if(uf.get_edge(i) % 2 == 0)
    {
      bool t = false;
      r = dfs(dfs, i, -1, t);
    }
    else
      r = dfs(dfs, i, -1, f);
    if(r > 0)
    {
      if(i >= n)
      {
        vp.emplace_back(r, i);
      }
      else
      {
        vp.emplace_back(i, r);
      }
    }
  }
  if(question == std::pair<int, int>(-1, -1) and (int)vp.size() % 2 == 1)
  {
    cout << -1 << "\n";
    return;
  }
  for (int i = 0; i + 1 < (int)vp.size(); i += 2)
  {
    res.emplace_back(vp[i].first, vp[i].second, vp[i + 1].second);
    res.emplace_back(vp[i + 1].second, vp[i].first, vp[i + 1].first);
  }
  if((int)vp.size() % 2 == 1)
  {
    res.emplace_back(question.first, question.second + n, vp.back().second);
    res.emplace_back(vp.back().second, question.first, vp.back().first);
  }
  cout << (int)res.size() << "\n";
  if(E == 1)
  {
    for(auto [t, p, q] : res)
    {
      if(t >= n)
      {
        cout << "C " << t - n + 1 << " " << p + 1 << " " << q + 1 << "\n";
      }
      else
      {
        cout << "R " << t + 1 << " " << p - n + 1 << " " << q - n + 1 << "\n";
      }
    }
  }
}

int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int kkt = 1;
  cin >> kkt;
  while(kkt--)
  {
    solve();
  }

  return 0;
}

じゅぴろの日記(⋈◍＞◡＜◍)。✧♡

April Challenge 2021 PAIRFLIP

解説

グラフ全体の辺の数が偶数の時．

グラフ全体の辺の数が奇数の時．