http://poj.org/problem?id=3740
这是一道搜索+回溯的题目，也是我第一次接触到回溯。
题意就是找一些行，这些行可以使每一列都只存在一个1。
深搜加回溯：
memory：118K c++ runtime:674ms。
#include <stdio.h>
#include <string.h>
#include <iostream> using namespace std; int a[][],n,m;
bool used[],fin; bool judge() //判断是否已经寻找到那些行加起来可以使所有的列只存在一个1。
{
for(int i=;i<=m;i++)
if(!used[i]) return false;
return true;
}
bool check(int row) //判断当前行是否有与之前行在某一列有冲突（都有1）
{
for(int i=;i<=m;i++)
if(used[i]&&a[row][i]) return false; // 如果都有1的话，回溯。
for(int i=;i<=m;i++)
if(a[row][i]) used[i]=true; //如果不冲突的话，则把这一行用上，并把其的所有的1所在的行都标记上。
return true;
} void dfs(int s)
{
if(fin||s>n+) return; //判断退出的标志，即输出的结果，或者行数已经超过了n+1。
if(judge()) {
printf("Yes, I found it\n");
fin=true;
return;
}
for(int i=s;i<=n&&!fin;i++)
{
if(check(i)){
dfs(i+);
for(int j=;j<=m;j++) //这就是回溯，因为如果I+1与之前的有冲突的话，if（check（i+1））则为false。所以执行的就应该是这一行。
if(a[i][j]) used[j]=false;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
fin=false;
memset(used,false,sizeof(used));
dfs();
if(!fin) printf("It is impossible\n");
}
return ;
}