[POJ 3740] Easy Finding【DLX】

• 2018-01-27
• 0
• 0

Problem:

Description

Input

Output

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

Solution:

这道题实际上可以直接 DFS 水过的。。然而我还是要认真研究 Dancing Links。

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

上图即为 Dancing Links 的模型，其中 h 为链表头，A ~ G 为列首，其余的每个点代表一个 1。

对于每个节点 i，需要维护其上下左右的四个节点 U[i], D[i], L[i], R[i] 以及所属列的列首 C[i]。

对于每一列 c，需要维护列元素数 S[c]（即上图中列首所标的数）。

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) 和恢复 (restore) 操作。

而 Dancing Links 可以简便地实现这两个操作。

【移除 (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]]++;

搜索时，Dancing Links 的矩阵通常缩小得很快，所以能优化时间。

需要细细体会一番 ~~

更详细的解释参见 http://blog.csdn.net/xiexingshishu/article/details/43064259。

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;

struct Dancing_Link{
	// The 0-th point is the head of dancing link
	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]]++;
	}
	
	inline void addline(int *col, int col_size){  // Add a new line
		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])
				add(C[j]);
		}
		add(c);
		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;
			}
			dl.addline(col, col_size);
		}		
		if(dl.dance()) puts("Yes, I found it");
		else puts("It is impossible");
	}
	return 0;
}