Easy Finding

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 19052		Accepted: 5273

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

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.

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

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

Yes, I found it

It is impossible

POJ Monthly Contest - 2009.08.23, MasterLuo

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <cctype>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#include <bitset>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define rb(a) scanf("%lf", &a)

#define rf(a) scanf("%f", &a)

#define pd(a) printf("%d\n", a)

#define plld(a) printf("%lld\n", a)

#define pc(a) printf("%c\n", a)

#define ps(a) printf("%s\n", a)

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int S[maxn], head[maxn], vis[maxn];

int U[maxn], D[maxn], L[maxn], R[maxn];

int C[maxn], X[maxn];

int n, m, ans, ret;

void init()

{

    for(int i = ; i <= m; i++)

        D[i] = i, U[i] = i, R[i] = i + , L[i] = i - ;

    L[] = m, R[m] = ;

    mem(S, ), mem(head, -);

    ans = m + ;

}

void delc(int c)

{

    L[R[c]] = L[c], R[L[c]] = R[c];

    for(int i = D[c]; i != c; i = D[i])

        for(int j = R[i]; j != i; j = R[j])

            U[D[j]] = U[j], D[U[j]] = D[j], S[C[j]]--;

}

void resc(int c)

{

    for(int i = U[c]; i != c; i = U[i])

        for(int j = L[i]; j != i; j = L[j])

            U[D[j]] = j, D[U[j]] = j, S[C[j]]++;

    L[R[c]] = c, R[L[c]] = c;

}

void add(int r, int c)

{

    ans++, S[c]++, C[ans] = c, X[ans] = r;

    D[ans] = D[c];

    U[ans] = c;

    U[D[c]] = ans;

    D[c] = ans;

    if(head[r] < ) head[r] = L[ans] = R[ans] = ans;

    else L[ans] = head[r], R[ans] = R[head[r]],L[R[head[r]]] = ans, R[head[r]] = ans;

}

bool dfs(int sh)

{

    if(!R[])

    {

        ret = sh;

        return true;

    }

    int c = R[];

    delc(c);

    for(int i = D[c]; i != c; i = D[i])

    {

        vis[sh] = i;

        for(int j = R[i]; j != i; j = R[j])

            delc(C[j]);

        if(dfs(sh + )) return true;

        for(int j = L[i]; j != i; j = L[j])

            resc(C[j]);

    }

    resc(c);

    return false;

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        init();

        int tmp;

        for(int i = ; i <= n; i++)

            for(int j = ; j <= m; j++)

            {

                rd(tmp);

                if(tmp) add(i, j);

            }

        if(dfs())

            printf("Yes, I found it\n");

        else

            printf("It is impossible\n");

    }

    return ;

}