POJ 3740

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 ;
}
上一篇:Linux上安装oracle客户端及sqlldr


下一篇:深入理解Java虚拟机类加载机制