poj 1166 The Clocks BFS or 高斯消元

這種題一看到就可以想到暴力搜尋，不過用高斯消元解同餘方程組應該可以做，但我還是沒做出來。

聽别人說是由于mod 是 4不是素數，是以高斯消元過程中對4取餘會導緻解集增大，過程中就不能取餘了，但是好像

消元後得到的解集也不是正确的，一直在疑惑中，希望路過的大牛們指點下如何用高斯消元解

另外附上我很挫的bfs代碼

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n = 9 , mm = -1;
int a[11][11];
int x[11] ,ansx[11];
void init()
{
	memset(a , 0,sizeof(a));
	for(int i = 0;i < n; i++)
		a[i][i] = 1;
	a[1][0] = a[3][0] = a[4][0] = 1;
	a[0][1] = a[2][1]= 1;
	a[1][2] = a[4][2] = a[5][2] = 1;
	a[0][3] = a[6][3] = 1;
	a[1][4] = a[3][4] = a[5][4] = a[7][4] = 1;
	a[2][5] = a[8][5] = 1;
	a[3][6] = a[4][6] = a[7][6] = 1;
	a[6][7] = a[8][7] = 1;
	a[4][8] = a[5][8] = a[7][8] = 1;
}
void dfs(int cur)
{
	int i,j;
	if(cur == n)
	{
		int ok = 1;
		for(i = 0;i < n ;i++)
		{
			int sum = 0;
			for(j = 0;j < n; j++)
				sum += x[j]*a[i][j];
			sum += a[i][n];
			sum %= 4;
			if(sum!=0)
				ok = 0;
			if(!ok)
				break;
		}
		if(ok)
		{
			int sum = 0;
			for(i = 0;i < n; i++)
				sum += x[i];
		//	printf("sum  = %d\n",sum);
			for(i = 0;i < n; i++)
				ansx[i] = x[i];
		}
		return ;
	}
	for(i = 0;i < 4; i++)
	{
		x[cur] = i;
		dfs(cur+1);
	}
}
int main()
{
	init();
	int i;
	for(i = 0;i < n; i++)
		scanf("%d", &a[i][n]);
	dfs(0);
	for(i = 0;i < n ;i++)
		while(ansx[i]--)
			printf("%d ", i+1);
	puts("");
}