Vision_数据结构_舞蹈连

2024-04-29 13:18
文章标签 数据结构 vision 舞蹈

本文主要是介绍Vision_数据结构_舞蹈连，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

///定义（ctrl+c）：
/*
    （1）历史：
　　     X算法是高德纳提出的解决精确覆盖问题的算法，而dancing links X算法则是DonKnuth(《计算机程序设计艺术》
         的作者)提出的对X算法的一种高效实现，这种实现建立在如上所说的矩阵表示法上。


    （2）算法思想：
        由如上精确覆盖问题的矩阵表示法中，我们知道dancing links x 是用来求解一个 01矩阵中选取哪几行可以使得
        这几行每一列都有且仅有一个1（就是每个元素在这几个子集里有且仅有出现过一次）。先不管他的实际意义，
        我们需要做的就是在一个01矩阵的选取某几行使之符合上述条件。我们很容易就想到枚举，然后判断符不符合条件，
        但是这个做法实在是太消耗时间。dacing links x就是一个高效的求解该类问题的算法，而这种算法，基于交叉十字
        循环双向链的数据结构。
    （3）精确覆盖问题的定义：
        给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1
    （4）重复覆盖问题：
        即选取一个01矩阵中的几行，使这几行组成的新矩阵的每一列至少有一个1。 
        该问题在精确覆盖问题上减少了一个约束条件
    （5）应用：
        解决精确覆盖问题和重复覆盖问题
    
*/
///代码：


/*
**name:舞蹈连-精确覆盖问题
**function:给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1
**输入参数：包含1的位置（i,j）
**输出参数：行集合的信息
*/
#include <iostream>
#include <cstdio>
using namespace std;const int maxnode = 100010;
const int maxm = 1010;
const int maxn = 1010;struct DLX{int n,m,len;int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];int H[maxn];//行头结点int S[maxm];//每列有多少个结点int ansd,ans[maxn];//如果有答案，则选了ansd行，具体是哪几行放在ans[]数组里面,ans[0~ansd-1]void init(int _n,int _m){n = _n;m = _m;for(int i = 0; i <= m; i++){S[i] = 0;U[i] = D[i] = i;//初始状态时，上下都指向自己L[i] = i-1;R[i] = i+1;}R[m] = 0,L[0] = m;len = m;//编号，每列都有一个头结点，编号1~mfor(int i = 1; i <= n; i++)H[i] = -1;//每一行的头结点}void link(int r,int c){//第r行，第c列++S[Col[++len]=c];//第len个节点所在的列为c,当前列的结点数++Row[len] = r;//第len个结点行位置为rD[len] = D[c];U[D[c]] = len;U[len] = c;D[c] = len;if(H[r] < 0)H[r] = L[len] = R[len] = len;else{R[len] = R[H[r]];L[R[H[r]]] = len;L[len] = H[r];R[H[r]] = len;}}void del(int c){//删除结点c，以及c上下结点所在的行//每次调用这个函数，都是从列头节点开始向下删除，这里c也可以理解为第c列//因为第c列的列头节点编号为cL[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[Col[j]];}}}void resume(int c){//回复结点c，以及c上下节点所在的行(同上，也可以理解为从第c列的头节点开始恢复for(int i = U[c]; i != c; i = U[i]){for(int j = L[i]; j != i; j = L[j]){++S[Col[U[D[j]]=D[U[j]]=j]];}}L[R[c]] = R[L[c]] = c;}bool dance(int d){//递归深度if(R[0] == 0){ansd = d;return true;}int c = R[0];for(int i = R[0]; i != 0; i = R[i]){if(S[i] < S[c])c = i;}del(c);//找到结点数最少的列，当前元素不是原图上0，1的节点，而是列头节点for(int i = D[c]; i != c; i = D[i]){ans[d] = Row[i];//列头节点下面的一个节点for(int j = R[i]; j != i; j = R[j])del(Col[j]);if(dance(d+1))//找到，返回return true;for(int j = L[i]; j != i; j = L[j])resume(Col[j]);}resume(c);return false;}
};DLX head;int main(){int n,m,k;while(~scanf("%d%d%d",&n,&m,&k)){head.init(n,m);for(int i = 1,x; i <= n; i++){for(int j = 1;j<=m;j++){scanf("%d",&x);if(!x)head.link(i,j);}}if(!head.dance(0))printf("NO\n");else{printf("%d\n",head.ansd);for(int i = 0; i < head.ansd; i++)printf(" %d",head.ans[i]);printf("\n");}}return 0;
}




/*
**name: 舞蹈连-重复覆盖问题
**function: 即选取一个01矩阵中的几行，使这几行组成的新矩阵的每一列至少有一个1。 
**输入参数：包含1的位置（i,j）
**输出参数：至少所消耗的行数，如果返回无穷大则表明不存在
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct DLX
{int n,m,len,ansd;int S[400],U[200000],D[200000],L[200000],R[200000],Row[200000],Col[200000];int H[400];void init(int _n,int _m){n=_n;m=_m;len=m;ansd=0x3f3f3f3f;for(int i=0; i<=m; i++){S[i]=0;U[i]=D[i]=i;R[i]=i+1;L[i]=i-1;Row[i]=0;Col[i]=i;}R[m]=0;L[0]=m;for(int i=1; i<=n; i++)H[i]=-1;}void link(int r,int c){++len;++S[c];Row[len]=r;Col[len]=c;D[len]=D[c];U[D[c]]=len;U[len]=c;D[c]=len;if(H[r]==-1){H[r]=R[len]=L[len]=len;}else{R[len]=R[H[r]];L[R[H[r]]]=len;L[len]=H[r];R[H[r]]=len;}}int f(){int ans=0;int V[400];memset(V,0,sizeof(V));for(int i=R[0]; i!=0; i=R[i]){V[i]=true;}for(int i=R[0]; i!=0; i=R[i]){if(V[i]){ans++;V[i]=false;for(int j=D[i]; j!=i; j=D[j]){for(int k=R[j]; k!=j; k=R[k]){V[Col[k]]=false;}}}}return ans;}void del(int c){for(int i=D[c]; i!=c; i=D[i]){R[L[i]]=R[i];L[R[i]]=L[i];}}void resume(int c){for(int i=U[c]; i!=c; i=U[i]){L[R[i]]=i;R[L[i]]=i;}}void Dance(int d){if(d>=ansd)return ;if(d+f()>=ansd)return ;if(R[0]==0){ansd=min(ansd,d);return ;}int c=R[0];for(int i=R[0]; i!=0; i=R[i]){if(S[i]<S[c])c=i;}for(int i=D[c]; i!=c; i=D[i]){del(i);for(int j=R[i]; j!=i; j=R[j])del(j);Dance(d+1);for(int j=L[i]; j!=i; j=L[j])resume(j);resume(i);}return ;}
};
DLX head;
int main(){int n,m,k,x;while(~scanf("%d%d%d",&n,&m,&k)){head.init(n,m);for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){scanf("%d",&x);if(!x)head.link(i,j);}}head.Dance(0);if(head.ansd<=k&&head.ansd!=0x3f3f3f3f)printf("yes\n");else printf("no\n");//printf("%d\n",head.ansd);}return 0;
}




/*
**name:舞蹈连-精确覆盖问题
**function:求解数独
**输入参数：数独盘的字符串
**输出参数：完整的数独盘字符串
*/
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <algorithm>using namespace std;
const int maxn=1000,maxm=400,maxnode=400000;
struct DLX
{int n,m,len;int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];int H[maxn];///行头结点int S[maxm];///每列有多少个结点int ansd,ans[maxn];void init(int _n,int _m){n=_n;m=_m;for(int i=0; i<=m; i++){S[i]=0;U[i]=D[i]=i;L[i]=i-1;R[i]=i+1;}R[m]=0,L[0]=m;len=m;for(int i=1; i<=n; i++){//cout<<"**"<<endl;H[i]=-1;}}void link(int r,int c){++S[Col[++len]=c];Row[len]=r;D[len]=D[c];U[D[c]]=len;U[len]=c;D[c]=len;if(H[r]<0)H[r]=L[len]=R[len]=len;else{R[len]=R[H[r]];L[R[H[r]]]=len;L[len]=H[r];R[H[r]]=len;}}void del(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[Col[j]];}}}void resume(int c){for(int i=U[c]; i!=c; i=U[i]){for(int j=L[i]; j!=i; j=L[j]){++S[Col[U[D[j]]=D[U[j]]=j]];}}L[R[c]]=R[L[c]]=c;}bool dance(int d){//cout<<d<<endl;if(R[0]==0){ansd=d;return true;}int c=R[0];///找一个1少的列,相当于剪枝了for(int i=R[0]; i!=0; i=R[i]){//cout<<S[i]<<endl;if(S[i]<S[c]){c=i;}}del(c);//cout<<S[1]<<endl;//cout<<"del()"<<c<<endl;//cout<<D[c]<<" "<<endl;for(int i=D[c]; i!=c; i=D[i]){//cout<<i<<endl;ans[d]=Row[i];for(int j=R[i]; j!=i; j=R[j]){del(Col[j]);}if(dance(d+1))return true;for(int j=L[i]; j!=i; j=L[j]){resume(Col[j]);}}resume(c);return false;}
};
struct node
{int pos;int data;int lie;
} q[2000];
DLX head;
int main()
{char s[100];while(scanf("%s",s)){if(strcmp(s,"end")==0)break;int len=strlen(s);head.init(1000,324);int row=0;for(int i=0; i<len; i++){int x=i/9,y=i%9;if(s[i]=='.'){for(int j=1; j<=9; j++){//x行y列填了一个数字head.link(++row,x*9+(y+1));//x行填了一个数字jhead.link(row,x*9+j+81);//y列填了一个数字jhead.link(row,y*9+j+162);//g宫填了一个数字jint xx=x/3*3,yy=y/3*3;int g=xx/3*3+yy/3+1;head.link(row,(g-1)*9+j+243);q[row].pos=i;q[row].data=j;q[row].lie=x*9+y+1;}}else{int a=s[i]-'0';//x行y列填了一个数字head.link(++row,x*9+(y+1));//x行填了一个数字jhead.link(row,x*9+a+81);//y列填了一个数字jhead.link(row,y*9+a+162);//g宫填了一个数字jint xx=x/3*3,yy=y/3*3;int g=xx/3*3+yy/3+1;head.link(row,(g-1)*9+a+243);q[row].pos=i;q[row].data=a;q[row].lie=x*9+y+1;}}//cout<<head.S[1]<<endl;bool ok=head.dance(0);//cout<<ok<<endl;//cout<<head.ansd<<endl;for(int i=0; i<head.ansd; i++){if(s[q[head.ans[i]].pos]=='.')s[q[head.ans[i]].pos]='0'+q[head.ans[i]].data;}//cout<<endl;printf("%s\n",s);}return 0;
}



///扩展：
/*
    舞蹈连的步骤：
        1、从矩阵中选择一行
        2、根据定义，标示矩阵中其他行的元素
        3、删除相关行和列的元素，得到新矩阵
        4、如果新矩阵是空矩阵，并且之前的一行都是1，那么求解结束，跳转到6；新矩阵不是空矩阵，
    继续求解，跳转到1；新矩阵是空矩阵，之前的一行中有0，跳转到5
        5、说明之前的选择有误，回溯到之前的一个矩阵，跳转到1；如果没有矩阵可以回溯，说明该问题无解，跳转到7
        6、求解结束，把结果输出
        7、求解结束，输出无解消息
*/

这篇关于Vision_数据结构_舞蹈连的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/946193。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2