C2. Binary Table (Hard Version)

  • Quiz
  • AC
  • 解法
    • 下の2行以外は0になるようにする
    • 最下段2行のみに1がある状態になったら、1を右に寄せていく
    • 右下の2x2領域にのみ1がある状態になるので、その状態になれば最悪でも4手で全て0にできる
  • 感想
    • 最後の2x2領域のパターンが24=16通りあって手書きを避けるようにしてみた→うまくいった
    • 「答えの登録・状態変更・略記」のためにラムダ関数を導入(下記コードでいうreg)したが良かった
    • 筋肉実装問題という印象だが、試みが上手くいったのでやってよかった
// for codeforces
void solve(){
  ll H,W;cin>>H>>W;
  VV A(H, VI(W));
  rep(i,H){
    string s;cin>>s;
    rep(j,W){
      char c = s[j];
      ll v = c-'0';
      A[i][j]=v;
    }
  }

  // 答え
  VV Ans;

  // (y,x,y,x,y,x)の順に入力し、その3点の値を反転させる
  auto reg = [&](ll a, ll b, ll c, ll d, ll e, ll f){
    Ans.push_back({a,b,c,d,e,f});
    // 状態も更新する
    A[a][b] = 1-A[a][b];
    A[c][d] = 1-A[c][d];
    A[e][f] = 1-A[e][f];
  };

  // 下2行を残して他は0にする（下の行に1を押し付ける）
  rep(i,H-2){
    rep(j,W-1){
      if(A[i][j]==0 && A[i][j+1]==0)continue;
      if(A[i][j]==1 && A[i][j+1]==1){
        reg(i,j, i,j+1, i+1,j); continue;
      }
      if(A[i][j]==0 && A[i][j+1]==1){
        reg(i,j+1, i+1,j, i+1,j+1); continue;
      }
      if(A[i][j]==1 && A[i][j+1]==0){
        reg(i,j, i+1,j, i+1,j+1); continue;
      }
    }
  }
  // この結果、最下2段にのみ0,1が存在する
  // 1を右に寄せていく
  rep(i,W-2){
    if(A[H-2][i]==0 && A[H-1][i]==0)continue;
    
    if(A[H-2][i]==1 && A[H-1][i]==1){
      if(A[H-2][i+1]==1){
        reg(H-2,i, H-1,i, H-2,i+1);
      }
      else{
        reg(H-2,i, H-1,i, H-1,i+1);
      }
      continue;
    }

    if(A[H-2][i]==0 && A[H-1][i]==1){
      reg(H-1,i, H-2,i+1, H-1,i+1);
      continue;
    }    

    if(A[H-2][i]==1 && A[H-1][i]==0){
      reg(H-2,i, H-2,i+1, H-1,i+1);
      continue;
    }
  }

  // 最後に右下の処理
  while(true){
    ll cnt=0;
    cnt += A[H-2][W-2];
    cnt += A[H-1][W-2];
    cnt += A[H-2][W-1];
    cnt += A[H-1][W-1];
    if(cnt==0){
      // 何もしなくていい
      break;
    }
    else if(cnt==1 or cnt==2){
      // 0を2つ選ぶ
      VI V;
      rep(i,2){
        rep(j,2){
          ll y = H-2+i;
          ll x = W-2+j;
          if(A[y][x]==0 && V.size()<4){
            V.push_back(y);
            V.push_back(x);
          }
        }
      }
      // 1を1つ選ぶ
      rep(i,2){
        rep(j,2){
          ll y = H-2+i;
          ll x = W-2+j;
          if(A[y][x]==1 && V.size()<6){
            V.push_back(y);
            V.push_back(x);
          }
        }
      }
      assert(V.size()==6);
      reg(V[0],V[1],V[2],V[3],V[4],V[5]);      
    }
    else if(cnt==3){
      VI V;
      rep(i,2){
        rep(j,2){
          ll y = H-2+i;
          ll x = W-2+j;
          if(A[y][x]==1){
            V.push_back(y);
            V.push_back(x);
          }
        }
      }
      assert(V.size()==6);
      reg(V[0],V[1],V[2],V[3],V[4],V[5]);
    }
    else
    // cnt=4
    {
      // どれか3つを反転させてcnt=1に遷移させる
      reg(H-2,W-2, H-1,W-2, H-1,W-1);
    }
  }

  {
    // 全て0になっているか確認
    ll sum=0;
    rep(i,H){
      rep(j,W){
        sum += A[i][j];
      }
    }
    assert(sum==0);
  }
  
  // answer
  ll sz = SZ(Ans);
  debug(sz, H*W);
  p(sz);
  rep(i,sz){
    print_vector(Ans[i]);
  }
}

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

    // input
    ll N; 
    cin>>N;
    
    rep(test_id,N){
      debug(test_id);
      solve();
    }
    
    return 0;
}