POJ 3740 Easy Finding题解

简介: 这篇文章提供了一个使用舞蹈链(Dancing Links)算法解决POJ 3740 "Easy Finding" 问题的C++代码实现,该问题要求找出矩阵中能够使每一列都恰好包含一个1的行集合。

POJ 3740 Easy Finding

Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you
find some rows that let every cloumn contains and only contains one 1.

Input

There are multiple cases ended by EOF. Test case up to 500.The first line of input is M, N (M ≤ 16, N ≤ 300). The next M lines every line contains N integers separated by space.

Output

For each test case, if you could find it output “Yes, I found it”, otherwise output “It is impossible” per line.

Sample Input

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

Sample Output

Yes, I found it
It is impossible

这是用舞蹈链解决的一个精准覆盖问题的模板题

#include <cstdio>
#include <cstring>
const int M = 20*310+310;
int n,m,s;
int Up[M],Down[M],Left[M],Right[M];
int Col[M],Row[M];
int Head[M];
int S[M];
int ansR,ans[M];

void pre()
{
    for(int i=0;i<=m;i++)
    {
        Up[i]=i;
        Down[i]=i;
        Left[i]=i-1;
        Right[i]=i+1;
        Col[i]=i;
        Row[i]=0;
        S[i]=0;
    }
    Left[0]=m;
    Right[m]=0;
    s=m;
    for(int i=0;i<=n;i++)
    {
        Head[i]=-1;
        ans[i]=0;
    }
    ansR=0;
}

void Insert(int r,int c)
{
    s++;
    Down[s]=Down[c];
    Up[s]=c;
    Up[Down[c]]=s;
    Down[c]=s;

    Row[s]=r;
    Col[s]=c;
    S[c]++;
    if(Head[r]<0)
    {
        Head[r]=s;
        Right[s]=s;
        Left[s]=s;
    }
    else
    {
        Left[s]=Head[r];
        Right[s]=Right[Head[r]];
        Left[Right[Head[r]]]=s;
        Right[Head[r]]=s;
    }
}

void Remove(int c)
{
    Left[Right[c]]=Left[c];
    Right[Left[c]]=Right[c];
    for(int i=Down[c];i!=c;i=Down[i])
    {
        for(int j=Right[i];j!=i;j=Right[j])
        {
            Up[Down[j]]=Up[j];
            Down[Up[j]]=Down[j];
            --S[Col[j]];
        }
    }
}

void Resume(int c)
{
    for(int i=Up[c];i!=c;i=Up[i])
    {
        for(int j=Left[i];j!=i;j=Left[j])
        {
            Down[Up[j]]=j;
            Up[Down[j]]=j;
            ++S[Col[j]];
        }
    }
    Right[Left[c]]=c;
    Left[Right[c]]=c;
}

bool Dance(int Deep)
{
    if(Right[0]==0)
    {
        ansR=Deep;
        return true;
    }
    int c=Right[0];
    for(int i=Right[0];i!=0;i=Right[i])
        if(S[i]<S[c])c=i;
    Remove(c);
    for(int i=Down[c];i!=c;i=Down[i])
    {
        ans[Deep]=Row[i];
        for(int j=Right[i];j!=i;j=Right[j])
        {
            Remove(Col[j]);
        }
        if(Dance(Deep+1))return true;
        for(int j=Left[i];j!=i;j=Left[j])
            Resume(Col[j]);
    }
    Resume(c);
    return false;
}

int main()
{
    int t;
    while(~scanf("%d%d",&n,&m))
    {
        pre();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&t);
                if(t)
                {
                    Insert(i,j);
                }
            }
        }
        bool flag=true;
        for(int i=1;i<=m;i++)
        {
            if(S[i]==0)
            {
                flag=false;
                break;
            }
        }
        if(flag&&Dance(1))
        {
            printf("Yes, I found it\n");
        }
        else printf("It is impossible\n");
    }
    return 0;
}
相关文章
[WMCTF2020]easy_re 题解
[WMCTF2020]easy_re 题解
131 0
|
存储
easy_Maze 题解
easy_Maze 题解
77 1
|
网络架构
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
124 0
Leetcode-Easy 412. Fizz Buzz
Leetcode-Easy 412. Fizz Buzz
93 0
Leetcode-Easy 412. Fizz Buzz
Leetcode-Easy 70. Climbing Stairs
Leetcode-Easy 70. Climbing Stairs
107 0
Leetcode-Easy 70. Climbing Stairs
|
算法 测试技术
【算法笔记题解】PAT A1075 PAT Judge
【算法笔记题解】PAT A1075 PAT Judge
【算法笔记题解】PAT A1075 PAT Judge
|
Java 文件存储
HDOJ(HDU) 2132 An easy problem
HDOJ(HDU) 2132 An easy problem
129 0
|
Java 文件存储
HDOJ(HDU) 2123 An easy problem(简单题...)
HDOJ(HDU) 2123 An easy problem(简单题...)
192 0

热门文章

最新文章