#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MAX 100

char *mat[MAX * MAX];
int N, M;

void out(void)
{
	int i, j;
	for(i = 0; i < M; i++)
	{
		for(j = 0; j <= N; j++)
		{
			putchar('0' + mat[i][j]);
			putchar(' ');
		}
		putchar('\n');
	}
	puts("----------");
}

void solve(void)
{
	int i, j, k;
	int nextj = 0;
	char *t;
	out();
	for(i = 0; i < M && nextj < N; i++)
	{
		for(j = nextj; j < N; j++)
		{
			for(k = i; k < M; k++)
			{
				if(mat[k][j])
				{
					break;
				}
			}
			if(k < M)
			{
				break;
			}
		}
		if(j >= N)
		{
			break;
		}
		nextj = j + 1;
		t = mat[i];
		mat[i] = mat[k];
		mat[k] = t;
		for(k = i + 1; k < M; k++)
		{
			if(mat[k][nextj - 1])
			{
				for(j = nextj - 1; j <= N; j++)
				{
					mat[k][j] ^= mat[i][j];
				}
			}
		}
		out();
	}
	for(i = M - 1; i >= 0; i--)
	{
		for(j = 0; j < N; j++)
		{
			if(mat[i][j])
			{
				break;
			}
		}
		if(j >= N)
		{
			if(mat[i][N])
			{
				puts("-1");
				return;
			}
			else
			{
				continue;
			}
		}
		nextj = j;
		for(k = i - 1; k >= 0; k--)
		{
			if(mat[k][nextj])
			{
				for(j = nextj; j <= N; j++)
				{
					mat[k][j] ^= mat[i][j];
				}
			}
		}
		out();
	}
	k = 0;
	for(i = 0; i < M; i++)
	{
		k += mat[i][N];
	}
	printf("%d\n", k);
}

int main(void)
{
	int r, c;
	while(scanf("%d %d", &r, &c) != EOF)
	{
		int i, j;
		N = r + c;
		M = 0;
		for(i = 0; i < r; i++)
		{
			for(j = 0; j < c; j++)
			{
				int x;
				scanf("%d", &x);
				if(x != 0)
				{
					mat[M] = (char*)malloc(sizeof(char) * (N + 1));
					memset(mat[M], 0, sizeof(char) * (N + 1));
					mat[M][i] = 1;
					mat[M][j + r] = 1;
					mat[M][N] = (x < 0);
					M++;
				}
			}
		}
		solve();
		for(i = 0; i < M; i++)
		{
			free(mat[i]);
		}
	}
	return 0;
}

• t4 (72) t4 2006-02-25 13:33:07
  • the answer is always Impossible.. (76) TN 2006-02-25 13:34:10
  • 呵呵,这个强 (76) davydc 2006-02-25 14:05:57
• Re:t3 (4500) T3 2006-02-25 15:15:40