精确覆盖问题-舞蹈链-Easy Finding(WA)

Description

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

Code

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
#include <vector>
#define FOR(i,A,s) for(int i=A[s];i!=s;i=A[i])//i:变量，A:方向，s:起始与终止
using namespace std;

const int MAX_N=6e3;
int l[MAX_N],r[MAX_N],u[MAX_N],d[MAX_N],col[MAX_N],m,n;

void init(int mm,int nn){
    m=mm;n=nn;
    for(int i=0;i<=n;i++){
        l[i]=(i-1+n+1)%(n+1);r[i]=(i+1)%(n+1);
        u[i]=d[i]=i;
        col[i]=i;
    }
    int size=n+1;
    for(int i=1;i<=m;i++){
        int p=0;
        for(int j=1;j<=n;j++){
            int num;scanf("%d",&num);
            if(!num) continue;
            u[size]=u[j];d[size]=j;u[j]=size;d[u[size]]=size;
            if(!p){
                p=size;
                l[size]=r[size]=size;
            }
            else{
                l[size]=size-1;r[size]=p;
                l[p]=size;r[size-1]=size;
            }
            col[size++]=j;
        }
    }
}

void remove(int c){ //删除第c列包含1的所有行
    l[r[c]]=l[c];r[l[c]]=r[c];
    FOR(i,d,c){
        FOR(j,r,i){
            u[d[j]]=u[j];
            d[u[j]]=d[j];
        }
    }
}

void recover(int c){
    l[r[c]]=c;r[l[c]]=c;
    FOR(i,d,c){
        FOR(j,r,i){
            u[d[j]]=j;
            d[u[j]]=j;
        }
    }
}

bool dfs(){
    if(r[0]==0) return true;
    int c=r[0];
    remove(c);
    FOR(i,d,c){
        FOR(j,r,i) remove(col[j]);
        if(dfs()) return true;
        FOR(j,r,i) recover(col[j]);
    }
    recover(c);
}

int main(){
    //freopen("/Users/guoyu/Desktop/algorithm/in.txt", "r", stdin);
    int m,n;
    while(~scanf("%d%d",&m,&n)){
        init(m,n);
        if(dfs()) printf("Yes, I found it\n");
        else printf("It is impossible\n");
    }
    return 0;
}