#include<stdio.h>
#include<string.h>
#define M 20
#define N 310
int map[M][N],sum[N],tem[N];
int fin;
int n,m;
void find(int a[M][N],int b[N],int start,int cur)
{
	int j,k,flag;
	if (start==n)
		fin = 1;
	if (b[start]<1&&start<n)
	{
		for (j = 0;j<m;j++)
		{
			if (b[start]+a[j][start]==1&&j!=cur)
			{
				flag = 0;
				for (k = 0;k<n;k++)
				{
					if(b[k]+a[j][k]>1)
					{
						flag = 1;
						break;
					}
				}
				if (flag == 0)
				{
					for (k = 0;k<n;k++)
					{
						b[k]+=a[j][k];
						tem[k] = map[j][k];
						a[j][k] = 0;
					}
					find(a,b,start+1,cur);
					for (k = 0;k<n;k++)
					{
						b[k] -= tem[k];
						a[j][k] = tem[k];
					}
				}				
			}
		}
	}
	else if(b[start] == 1&&start<n)
		find(a,b,start+1,cur);
}
int main()
{
	int i,j;
	while (scanf ("%d%d",&m,&n) != EOF)
	{
		if (m == 0||n == 0)
		{
			printf ("It is impossible\n");
			continue;
		}
		memset(sum,0,sizeof(sum));
		for (i = 0; i< m;i++)
			for (j = 0; j< n; j++)
				scanf ("%d",&map[i][j]);
			for (i = 0; i< m;i++)
			{
				for (j = 0;j<n;j++)
				{
				   sum[j]+=map[i][j];
				}
				   fin = 0;
				   find(map,sum,0,i);
				   if (fin == 1)
					   break;
				   else memset(sum,0,sizeof(sum));
			}
			if (fin == 1)
				printf ("Yes, I found it\n");
			else printf ("It is impossible\n");
	}
	return 0;
}

• Re:大牛看看我的代码为啥老是WA，测试数据都对啊！ (20) looker 2009-08-23 17:39:39
  • Re:大牛看看我的代码为啥老是WA，测试数据都对啊！ (48) looker 2009-08-24 08:28:41