AOJ 1308 ICPC Asia resional 2010 Problem D: Awkward Lights

問題概要

nxmマスのパネルがある。
それぞれのパネルはONかOFFのいずれかである。

一つのパネルを押すと、そのパネルに加えてマンハッタン距離がちょうどdのパネルも全てON,OFFが反転する。
このとき、全てのパネルをOFFの状態にできるか答えよ。

制約条件

n,m≦25
d≦m+n

方針

スイッチ(k,l)がパネル(i,j)に影響をあたえるときa[(i,j)][(k,l)]=1,そうでないときa[(i,j)][(k,l)]=0という行列を考える。
a[(n,m)][(i,j)]=(i,j)の初期状態とする。

スイッチは二度押すと元に戻るので、mod 2でこの連立一次方程式を解き、解が存在すればいいかをみてやればよい。
連立一次方程式の解は掃きだし法により求めた。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1},dy2[]={1,-1,-1,1},dx2[]={1,1,-1,-1};
int m,n,d,s[25][25];
int main()
{
	while(scanf("%d%d%d",&n,&m,&d),m){
		int N=m*n;
		vector<vi> a(N,vi(N+1,0));
		rep(i,m)rep(j,n)scanf("%d",s[i]+j), a[i*n+j][N]=s[i][j];
		rep(i,N)(a[i][i]+=1)%=2;
		rep(i,m)rep(j,n)rep(dir,4)rep(k,d){
			int y=i+dy[dir]*d+dy2[dir]*k, x=j+dx[dir]*d+dx2[dir]*k;
			if(0<=y&&y<m&&0<=x&&x<n){
				(a[y*n+x][i*n+j]+=1)%=2;
			}
		}
		int j=0;
		rep(i,N){
			int mi=i;
			if(!a[mi][j])for(int k=i+1;k<N;k++)if(a[mi]<a[k]){
				mi=k;
				if(a[mi][j])break;
			}
			swap(a[i],a[mi]);
			for(;j<N&&a[i][j]==0;j++);
			if(j>=N)break;
			assert(a[i][j]);
			rep(k,N)if(i<k&&a[k][j])for(int l=j;l<=N;l++)(a[k][l]+=a[i][l])%=2;
			j++;
		}
		bool ok=1; j=0;
		rep(i,N)if(ok&&a[i][N]){
			for(;j<N&&a[i][j]==0;j++);
			if(j>=N)ok=0;
		}
		printf("%d\n",(int)ok);
	}
	return 0;
}