#include<stdio.h>
#include<string.h>

int map[17][301];
int rn[17];
int cn[301];
bool is_useful[17];
bool flag;
int M,N;
int i,j;
int tn[301];

void dfs(int depth, int total)
{
	if(flag)return;//has found

	if(total == N) //found!!
	{
		flag = true;
		return;
	}

	if(depth == M)return;

	if(!is_useful[depth]) //rn[depth] = 0
	{
		dfs(depth+1,total);
		return;
	}
	
	if(total + rn[depth] > N)//not ok
	{
		dfs(depth+1,total);
		return;
	}

	for(i=0;i<N;i++)
	{
		if(tn[i] !=0 && map[depth][i] !=0)//more than one 1
		{
			dfs(depth+1,total);
			return;
		}
	}
	//dont use the row
	dfs(depth+1,total);

	if(flag)return;//has found

	//use the row
	for(i=0;i<N;i++)
		tn[i] += map[depth][i];

	dfs(depth+1,total+rn[depth]);

	for(i=0;i<N;i++)
		tn[i] -= map[depth][i];
}
int main()
{
	int i,j;
	
	while(scanf("%d%d",&M,&N) != EOF)
	{
		for(i=0;i<M;i++)
		{
			rn[i]=0;
			is_useful[i]=true;
		}
		for(i=0;i<N;i++)
		{
			cn[i]=0;
			tn[i]=0;
		}
		
		flag = false;
	
		for(i=0;i<M;i++)
			for(j=0;j<N;j++)
			{
				scanf("%d",&map[i][j]);
			
				if(map[i][j]!=0)
				{
					rn[i]++; 
					cn[j]++;
				}
			}
		//if a rown == 0 then the row is useless
		for(i=0;i<M;i++)
			if(rn[i]==0)is_useful[i]=false;

		//if a coln == 0 then impossible
		for(i=0;i<N;i++)if(cn[i]==0)break;
		if(i!=N)
		{
			printf("It is impossible\n");
			continue;
		}
		
		dfs(0,0);

		if(flag)
			printf("Yes, I found it\n");
		else 
			printf("It is impossible\n");
	}

	return 0;
}

• Re:朴素DFS的孩子们，多加几个return就行了，500ms (1748) wcfairytale 2011-10-10 01:23:22
  • 加一条 = 500ms -> 260ms (0) wcfairytale 2011-10-10 01:24:09
    • 最后加一条 = 260ms -> 250ms 收工 (2049) wcfairytale 2011-10-10 01:36:45