# [POJ 3740] Easy Finding【DLX】

• 2018-01-27
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K

Description

Given a M×N matrix AAij ∈ {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 MN (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
```

Source

POJ Monthly Contest - 2009.08.23, MasterLuo

## Solution:

Dancing Links 是我们伟大的先驱高德纳 (Donald Knuth) 先生为了解决精确覆盖问题 (Exact Cover Problem) 所提出的 Algorithm X 中所用到的数据结构，其本质是一个双向循环十字链表

```ALGORITHM X(Depth, Matrix):
if Matrix.empty()
return true
choose a column c with the least number of elements
remove column c and each row r such that Matrix[r][c] == 1
for each row r such that Matrix[r][c] == 1
record row r in the solution
for each column j such that Matrix[r][j] == 1
remove column j and each row i such that Matrix[i][j] == 1
if X(Depth + 1, Matrix) == true
return true
for each column j such that Matrix[r][j] == 1
restore column j and each row i such that Matrix[i][j] == 1
restore column c and each row r such that Matrix[r][c] == 1
return false
```

【移除 (remove) 操作】

```remove(c)  // Remove the i-th column
L[R[c]] = L[c]
R[L[c]] = R[c]
for each point i in column c, enumerated forward
for each point j in the same row as i, enumerated forward
U[D[j]] = U[j]
D[U[j]] = D[j]
S[C[j]]--;
```

【恢复 (restore) 操作】

```restore(c)  // Restore the i-th column
L[R[c]] = c
R[L[c]] = c
for each point i in column c, enumerated backward
for each point j in the same row as i, enumerated backward
U[D[j]] = j
D[U[j]] = j
S[C[j]]++;```

## Code: O(玄学) [748K, 266MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int M, N, A;
int col[305], col_size;

int S[5000], C[5000];
// S[i]: The remaining number of the i-th column
// C[i]: The column in which the i-th point is
int U[5000], D[5000], L[5000], R[5000];
int topv;

inline void init(int col_num){  // Initialize col_num column heads
topv = col_num;
memset(S, 0, sizeof(S));
for(register int i = 0; i <= col_num; i++)
C[i] = U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1;
L[0] = col_num, R[col_num] = 0;
}

inline void del(int c){  // Remove the i-th column
L[R[c]] = L[c], R[L[c]] = R[c];
for(register int i = D[c]; i != c; i = D[i])
for(register int j = R[i]; j != i; j = R[j])
U[D[j]] = U[j], D[U[j]] = D[j], S[C[j]]--;
}

inline void add(int c){  // Restore the i-th column
L[R[c]] = R[L[c]] = c;
for(register int i = U[c]; i != c; i = U[i])
for(register int j = L[i]; j != i; j = L[j])
U[D[j]] = D[U[j]] = j, S[C[j]]++;
}

if(!col_size) return;
for(register int i = 1; i <= col_size; i++){
int &c = col[i];
C[++topv] = c;
L[topv] = topv - 1, R[topv] = topv + 1;
U[topv] = U[c], D[U[c]] = topv;
D[topv] = c, U[c] = topv;
S[c]++;
}
L[topv - col_size + 1] = topv, R[topv] = topv - col_size + 1;
}

inline bool dance(){  // Dance to search for the solution
if(R[0] == 0) return 1;  // The link is empty
int c = R[0];
for(register int i = R[c]; i; i = R[i])
if(S[i] < S[c]) c = i;  // Find the column with the least points
del(c);
for(register int i = D[c]; i != c; i = D[i]){  // Try every line
// We could record the chosen line here if necessary
for(register int j = R[i]; j != i; j = R[j])
del(C[j]);
if(dance()) return 1;
for(register int j = L[i]; j != i; j = L[j])
}
return 0;
}
} dl;

int main(){
while(scanf("%d%d", &M, &N) != EOF){
dl.init(N);
for(register int i = 1; i <= M; i++){
col_size = 0;
for(register int j = 1; j <= N; j++){
scanf("%d", &A);
if(A) col[++col_size] = j;
}
}
if(dl.dance()) puts("Yes, I found it");
else puts("It is impossible");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai