会津大学オンラインジャッジ 問131

Doctor's Strange Particles

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0131
博士の奇妙なライツアウトを題材にした問題。



ビット演算に置き換えて解。
一行目の押し方が決まれば残りの行は全自動で決まります。
というわけで一つのデータセットに対し１０２４通りを調べるだけです。
多分一番コードが長い人は行列演算を使って探索空間を狭めてるのだと思います。
このコードの成績、コードの短さ2/154位。
平凡な結果です。
ショートコードを狙ったわけではないのでまあこんなものです。

私の場合、コードや処理を簡潔にした結果として短くなっているだけです。
コードの簡潔さと難読化の境界線上に到達したらそれ以上コードを短くしません。


#include<stdio.h>


void calc(){
      int board[10],e,push[10],a,r,b,up,oldUp;
      int mask=(1<<10)-1;
      for(int i=0;i<10;i++){
            e=1;
            r=0;
            for(int j=0;j<10;j++){
                  scanf("%d",&a);
                  r+=e*a;
                  e=e<<1;
            }
            board[i]=r;
      }
      for(int p=0;p<=mask;p++){
            up=p;
            oldUp=0;
            bool hit=false;
            for(int k=0;k<10;k++){
                  push[k]=up;
                  a=up;
                  up=(board[k]^(oldUp)^(up<<1)^(up)^(up>>1))&mask;
                  oldUp=a;
                  if(k==9&&up==0){
                        hit=true;
                        break;
                  }
            }
            if(hit==true)break;
      }
      for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                  printf("%d%s",push[i]%2,j==9?"\n":" ");
                  push[i]/=2;
            }
      }
}


int main(){
      int n;
      scanf("%d",&n);
      while(n--){
            calc();
      }
}