dfs
View Code
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define maxn 20
#define maxm 305
int n, m;
int map[maxn][maxm];
int num[maxn];
bool g[maxn][maxn];
int rownum[maxn];
bool found;
void input()
{
memset(num, 0, sizeof(num));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
int a;
scanf("%d", &a);
if (a == 0)
map[i][j] = 0;
else
{
map[i][j] = 1;
num[i]++;
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
bool ok = true;
for (int k = 0; k < m; k++)
if (map[i][k] && map[j][k])
{
ok = false;
break;
}
if (ok)
g[i][j] = true;
else
g[i][j] = false;
}
}
void dfs(int tot, int now, int ans)
{
if (found)
return;
if (now == n)
{
if (ans == m)
found = true;
return;
}
dfs(tot, now + 1, ans);
bool ok = true;
for (int i = 0; i < tot; i++)
if (!g[rownum[i]][now])
{
ok = false;
break;
}
if (ok)
{
rownum[tot] = now;
dfs(tot + 1, now + 1, ans + num[now]);
}
}
int main()
{
//freopen("t.txt", "r", stdin);
while (scanf("%d%d", &n, &m) != EOF)
{
found = false;
input();
dfs(0, 0, 0);
if (found)
printf("Yes, I found it\n");
else
printf("It is impossible\n");
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110591.html原文链接：https://javaforall.net
