- 基本的には多色ライツアウトなので、(bitsetからvalarrayに変更した上で)排他的論理和をmod int演算に置き換えればよいです。
- ただし、掃き出すときに、最初になるべく1や3の要素を残すようにする必要があります。(3の回転を3回やれば1回分になりますが)2の回転から1回分を作ることはできないためです。
- それにしても、やはりまだ解の存在判定部分が苦手と感じた。 というか4x4/9x9は解が1対1対応しないので確認部分の実装が厳しい。
- 0解(quiet pattern)の重ね合わせを全探索して最短手数を出力する処理は未実装です。
tyama_henae26.cpp
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <valarray>
#include <algorithm>
#define coor(i,j) ((i)+(j)*m)
#define in(i,j) (0<=(i)&&(i)<m&&0<=(j)&&(j)<n)
using namespace std;
int main(){
int t=0,T,m,n,d=2;
int i,j,k;
int success,ans;
for(cin>>T;t<T;t++){
if(t)puts("");
printf("%d\n",t);
cin>>m;n=m;
vector<valarray<int>> M;
for(int i=0;i<m*n;i++)M.push_back(valarray<int>(m*n*2));
for(j=0;j<n;j++){
for(i=0;i<m;i++){
M[coor(i,j)][coor(i,j)]=1;
M[coor(i,j)][m*n+i+j*m]=1;
if(in(i-1,j))M[coor(i-1,j)][coor(i,j)]=3;
if(in(i+1,j))M[coor(i+1,j)][coor(i,j)]=3;
if(in(i,j-1))M[coor(i,j-1)][coor(i,j)]=3;
if(in(i,j+1))M[coor(i,j+1)][coor(i,j)]=3;
}
}
//solve
k=0;
for(i=0;i<m*n;i++){
for(j=k;j<m*n&&M[j][i]%2==0;j++);
if(j!=m*n){
swap(M[k],M[j]);
if(M[k][i]==3)M[k]*=3,M[k]%=4;
}else{
for(j=k;j<m*n&&M[j][i]%4!=2;j++);
if(j==m*n)continue; /// todo
swap(M[k],M[j]);
}
for(j=0;j<m*n;j++)if(j!=k&&M[j][i]){
if(M[j][i]==2)M[j]-=(M[k][i]==2?1:2)*M[k],M[j]+=8,M[j]%=4;
else if(M[j][i]==M[k][i])M[j]-=M[k],M[j]+=4,M[j]%=4;
else M[j]-=3*M[k],M[j]+=12,M[j]%=4;
}
k++;
}
map<string,int>ma;
for(i=0;i<k;i++){
int q;cin>>q;q=(5-q)%4;
int g=0;
for(j=0;j<i;j++)g+=M[j][i];
g%=4;
if((q-g)%M[i][i]){return -1;}
int f=(q-g+4)%4/M[i][i];
M[i]*=f,M[i]%=4;
if(g==q)continue;
for(j=m*n;j<m*n*2;j++){
for(int k=0;k<M[i][j]%4;k++)ma[to_string((j-m*n)%m+1)+" "+to_string((j-m*n)/m+1)]++;
}
}
for(;i<m*n;i++){
cin>>k;
// k...m*n: quiet patterns; implement searching shortest answer
}
for(auto &e:ma){
for(i=0;i<e.second%4;i++)cout<<e.first<<endl;
}
}
}
なお、以下のケースを3.85秒で解くことができます(2414手)。
ruby -e '40.times{puts 40.times.map{[*1..4].sample}*" "}'
1
40
3 3 3 3 4 3 2 3 2 3 2 2 3 2 4 2 4 1 4 3 3 2 3 4 3 2 4 1 2 1 4 3 4 1 1 3 2 3 1 4
3 3 4 3 1 4 3 3 2 3 3 4 4 1 4 3 4 3 1 4 3 4 4 3 4 2 3 3 2 4 3 2 4 1 2 3 4 1 3 1
3 3 4 3 2 1 2 1 1 3 3 2 2 2 3 2 4 3 1 1 1 4 4 4 4 2 1 4 4 3 4 2 3 2 2 2 3 3 3 3
2 3 1 3 3 2 2 4 2 3 3 1 1 1 1 2 4 1 3 4 3 3 4 1 2 3 3 1 4 2 1 1 1 1 1 3 2 3 2 1
4 2 2 3 4 2 2 3 2 4 4 2 4 4 1 4 3 1 1 3 2 4 4 4 3 2 2 3 3 1 4 2 4 1 4 1 2 3 3 2
1 2 1 4 3 1 1 1 1 4 1 1 4 1 2 3 3 1 2 3 3 2 2 4 3 3 1 4 3 4 1 2 2 3 4 4 1 4 3 1
4 2 1 3 1 3 4 4 4 2 4 2 4 1 2 4 3 3 1 2 1 2 2 1 4 1 4 2 1 2 4 3 2 3 2 2 3 2 1 2
1 3 3 4 3 3 1 3 4 4 4 1 1 2 1 2 2 3 3 1 2 1 3 2 4 3 2 4 1 1 2 4 1 4 4 1 2 3 1 3
2 2 4 1 2 1 2 1 3 2 1 4 3 3 3 4 3 1 1 4 1 4 1 2 2 3 4 4 4 3 1 3 1 1 4 4 3 3 3 4
2 2 4 2 1 3 3 3 3 1 2 3 4 1 3 2 1 1 3 3 1 1 2 2 1 3 3 2 3 4 2 3 3 3 2 4 1 3 4 2
2 4 1 4 2 4 4 2 1 2 3 1 3 3 3 3 2 3 4 2 3 3 1 2 2 2 2 3 1 1 1 1 4 4 1 4 1 2 2 4
1 3 2 3 1 2 1 3 2 4 4 2 4 3 2 1 2 2 2 4 1 1 1 4 3 4 4 3 1 1 2 2 1 1 3 1 4 4 4 1
4 1 3 2 4 3 1 2 3 3 4 3 1 4 3 3 4 4 1 3 1 3 1 2 4 2 3 1 2 1 2 3 2 2 1 1 1 4 4 2
1 4 3 4 1 2 4 3 1 4 4 3 4 2 2 3 4 1 3 3 2 2 3 4 1 2 1 2 4 4 2 1 1 1 3 4 1 2 1 1
3 2 2 1 3 1 2 3 4 1 2 1 1 3 2 1 2 4 2 2 4 4 3 2 1 1 4 4 4 3 1 3 1 4 1 4 3 2 2 3
2 1 3 3 1 3 2 2 4 2 1 3 2 3 2 2 2 4 4 1 1 4 3 4 3 2 1 4 1 4 3 1 4 1 1 2 2 2 2 4
3 1 2 3 2 4 4 3 4 1 1 1 2 2 1 1 1 2 4 4 2 1 2 3 1 4 3 1 1 4 3 1 1 1 4 3 2 1 3 2
3 1 1 3 2 4 1 3 1 4 2 3 4 1 1 4 4 3 3 3 2 1 2 2 3 3 1 1 2 1 3 3 1 2 1 4 3 1 1 2
3 2 1 4 1 2 1 2 3 3 2 1 4 1 3 3 2 1 4 3 1 2 4 2 3 1 2 4 3 3 1 1 3 4 4 1 2 2 1 2
2 4 1 3 1 1 2 1 3 2 3 4 3 4 2 4 2 2 3 2 4 3 4 3 3 3 4 3 1 2 1 1 2 2 2 1 3 2 1 2
2 1 3 2 1 4 1 1 4 4 3 2 1 4 1 4 4 4 2 1 1 4 2 4 1 3 3 3 2 3 3 4 1 4 4 3 3 4 4 3
4 2 3 3 2 2 4 4 3 1 2 2 4 1 4 1 3 3 4 2 1 3 3 3 1 1 3 1 2 4 4 1 2 1 4 4 4 2 1 1
1 1 3 4 3 3 3 2 4 3 3 1 3 2 2 3 2 2 1 2 3 4 1 2 2 1 1 2 1 2 1 4 1 1 4 4 2 1 1 3
2 4 1 3 4 1 3 3 3 1 1 4 1 1 3 1 2 3 1 2 2 2 2 1 2 1 3 1 3 3 1 3 4 2 4 1 3 3 4 1
2 1 4 3 2 2 4 2 2 4 3 4 3 1 3 3 2 4 4 2 2 2 4 3 4 3 4 4 1 2 1 2 2 3 1 1 2 3 2 1
2 3 4 4 2 3 2 4 2 4 3 3 4 4 4 1 4 3 1 3 3 4 2 2 3 4 1 4 1 4 2 1 1 3 2 2 1 2 2 1
1 4 3 1 2 3 2 4 4 3 4 1 1 2 1 3 4 4 4 1 1 2 4 1 2 2 1 3 3 1 2 2 4 2 3 4 4 4 4 3
1 1 1 4 2 2 4 2 1 2 1 3 3 4 4 1 3 4 3 2 4 4 1 3 1 1 1 4 3 4 3 2 3 1 1 1 4 1 1 2
1 3 4 2 2 2 1 3 4 1 2 2 1 2 4 2 4 4 2 1 1 4 4 1 3 1 3 3 2 1 1 1 4 4 1 4 1 1 2 3
2 3 1 3 2 1 4 3 2 1 3 4 2 1 4 4 2 1 2 4 1 2 1 1 4 2 1 4 3 2 2 1 2 2 2 3 1 3 1 2
2 2 2 4 2 3 3 2 3 4 2 4 1 2 4 2 3 3 4 2 4 1 1 4 4 3 4 1 3 3 3 4 4 2 4 4 3 3 3 4
1 2 1 2 4 4 4 2 3 1 2 1 1 2 2 4 1 4 4 2 2 2 2 4 2 3 2 4 3 2 2 2 3 1 2 2 1 1 2 1
2 2 3 1 2 2 2 4 1 2 3 2 3 2 2 1 2 3 2 1 3 2 1 2 4 1 2 3 4 4 2 1 2 4 1 2 4 4 2 1
3 2 1 1 3 2 4 2 1 3 2 3 3 3 3 4 2 3 2 1 2 1 1 4 4 4 2 4 3 1 4 3 3 2 3 2 1 2 2 2
2 2 3 1 2 2 1 3 4 2 2 2 2 4 2 4 1 4 4 3 2 3 3 4 2 4 2 3 2 2 2 1 2 4 1 3 1 4 2 4
2 4 1 2 2 2 1 3 1 2 1 4 4 1 4 3 2 3 1 3 3 2 1 1 2 1 3 3 4 4 4 2 1 1 3 4 2 2 4 2
4 1 1 2 2 2 2 3 3 2 2 1 1 3 2 2 1 1 3 1 1 1 1 1 4 3 2 4 1 2 3 4 2 1 4 4 4 4 4 2
1 3 3 2 1 4 4 4 1 4 1 1 3 2 4 1 4 2 4 1 2 2 2 3 2 1 2 1 1 2 2 1 4 1 1 4 1 1 1 3
4 2 2 4 4 2 3 1 4 4 4 1 1 2 2 1 2 4 1 2 1 1 4 4 3 2 3 2 3 3 3 3 2 4 3 3 3 3 2 2
1 3 2 2 2 4 1 3 4 1 3 2 1 2 1 1 4 1 3 3 4 1 2 4 2 3 2 2 4 4 1 1 1 2 2 4 4 4 3 1