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