#include <iostream>
#include <string>
using namespace std;
class easy
{
private:
	bool a[17][301];//第0行表示所有列的和，第0列表示行被选标志 
	int sum[301];//被选行的各列和 
	int m,n;//行数列数 
public:
	easy()
	{
		memset(a,false,sizeof(a));
		memset(sum,0,sizeof(sum));
	}
	void Input()
	{
		cin>>m>>n;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
			{	
				cin>>a[i][j];
				a[0][j]+=a[i][j];//各列的和 
			}
	}	
	void Find(int p)
	{
		for(int col=1;col<=n;col++)
			if(a[0][col]==0)//当这一列全为0时，肯定是不可能的
			{
				//a[0][0]=false;
				return;
			}
		if(a[0][0])//如果已经找到一组解，则停止搜索，此处可以剪枝 
			return; 
		bool flag;//该标志要用到两次 
		if(p>m)
		{
			flag=true;
			for(int k=1;k<=n&&flag;k++)
				if(sum[k]!=1)
					flag=false;
			a[0][0]=flag;//a[0][0]用来当find成功标记 
			return;
		}
		//a[p][0]=false;//标志该行不被选 
		Find(p+1);
		a[p][0]=true;//标志该行被选 
		flag=true;
		for(int j=1;j<=n&&flag;j++)
		{
			sum[j]+=a[p][j]; 
			if(sum[j]>1)//如果此时某一列的值已经大于等于2，则不往下搜索，剪枝 
				flag=false;
		}
		if(flag)
		{
			Find(p+1);
			for(int j=1;j<=n;j++)//还原 
				sum[j]-=a[p][j];
			a[p][0]=false;//标志还原 
		}
	}
	void Output()
	{
		if(a[0][0])
			cout<<"Yes, I found it"<<endl;
		else
			cout<<"It is impossible"<<endl;	
	}
};


int main()
{
	while(1)
	{
		easy e;
		e.Input();
		e.Find(1);
		e.Output();	
	}
	return 0;
}

• Re:DFS+剪枝，老是TLE (52) 36072219890803 2010-07-29 11:24:39