AOJ0131

問題:Doctor's Strange Particles
ライツアウトの解を求める。１個しか解がないと言う甘え仕様。
上から順番に処理していく。
まず1行目について全パターンの押し方を試す。
i行目はi-1行目を全て消さないと行けないので、押し方は一意に定まる。
そして一番下の行が全て消えていたらOK。
bitset便利。

#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;

void flip(vector<bitset<10> >& field, int y, int pos)
{
  field[y].flip(pos);
  if(pos+1<10)field[y].flip(pos+1);
  if(pos-1>=0)field[y].flip(pos-1);
  if(y+1<10)field[y+1].flip(pos);
  if(y-1>=0)field[y-1].flip(pos);
}

int main()
{
  int _;
  cin >> _;
  while(_--)
  {
    vector<bitset<10> > f(10,0);
    for(int i=0;i<10;++i)
    {
      int a;
      for(int j=0;j<10;++j)
      {
        cin >> a;
        if(a) f[i].flip(9-j);
      }
    }

    for(int v=0; v<(1<<10); ++v)
    {
      vector<pair<int,int> > ans;
      vector<bitset<10> > field = f;
      for(int i=0;i<10; ++i)
      {
        if(v&(1<<i))
        {
          flip(field,0,i);
          ans.push_back(make_pair(0,i));
        }
      }

      for(int j=1; j<10; ++j)
      {
        for(int k=0; k<10; ++k)
        {
          if(field[j-1][k])
          {
            flip(field,j,k);
            ans.push_back(make_pair(j,k));
          }
        }
      }

      bool clear = !field[9].any();
      if(clear)
      {
        sort(ans.begin(),ans.end());
        for(int i=0; i<10; ++i)
        {
          for(int j=0; j<10; ++j)
          {
            cout << binary_search(ans.begin(),ans.end(),make_pair(i,9-j));
            if(j!=9)cout << " ";
          }
          cout << endl;
        }
      }
    }
  }
  return 0;
}