[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:

这道题实际上可以直接 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;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
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