Dancing links 基础题

2024-08-24 11:58
文章标签 基础 links dancing

本文主要是介绍Dancing links 基础题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

全部都是数独类的题目


POJ 3074

</pre><pre name="code" class="cpp">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int M=1024*110;
const int N=1024;
char str[111];struct DLX
{int l[M], r[M], d[M], u[M], col[M], row[M], h[N], control[N];int dcnt;void init(int cols){memset(control,0,sizeof(control));memset(h,-1,sizeof(h));for(int i=0;i<=cols;i++){u[i]=d[i]=i;l[i]=i-1;r[i]=i+1;}r[cols]=0;l[0]=cols;dcnt = cols;}void remove(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];control[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])control[col[u[d[j]]=d[u[j]]=j]]++;r[l[c]]=l[r[c]]=c;}bool dance(int deep){if(r[0]==0){puts(str);return true;}int tempc=r[0];for(int i=r[0];i!=0;i=r[i])if(control[i]<control[tempc])tempc=i;remove(tempc);for(int i=d[tempc];i!=tempc;i=d[i]){str[row[i]/9]=row[i]%9+'1';for(int j=r[i];j!=i;j=r[j]) remove(col[j]);if(dance(deep+1)) return true;for(int j=l[i];j!=i;j=l[j]) resume(col[j]);}resume(tempc);return false;}inline void link(int x, int y){++control[col[++dcnt]=y];row[dcnt]=x;d[dcnt]=d[y];u[d[y]]=dcnt;u[dcnt]=y;d[y]= dcnt;if(h[x]<0)h[x]=l[dcnt]=r[dcnt]=dcnt;else{r[dcnt]=r[h[x]];l[r[h[x]]]=dcnt;l[dcnt]=h[x];r[h[x]]=dcnt;}}
}dlx;int main()
{
//	freopen("data.txt","r",stdin);while(~scanf("%s", str) && strcmp(str, "end")!=0){dlx.init(4*9*9);for(int i=0;i<9;i++)for(int j=0;j<9;j++)for(int k=1;k<=9;k++)if(str[i*9+j]=='.' || str[i*9+j]=='0'+k){int rr=i*9*9+j*9+k-1;dlx.link(rr, 81*0+i*9+k);dlx.link(rr, 81*1+j*9+k);dlx.link(rr, 81*2+(i/3+j/3*3)*9+k);dlx.link(rr, 81*3+i*9+j+1);}dlx.dance(0);}
}



POJ 3076

这个模板需要从第0行开始

否则无法进行递归

//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int M=4096*5;int l[M], r[M], d[M], u[M], col[M], row[M], h[4100], control[1030];
int dcnt = 0;
char str[16][17];inline void addnode(int &x)
{++x;r[x]=l[x]=u[x]=d[x]=x;
}inline void insert_row(int rowx, int x)
{r[l[rowx]]=x;l[x]=l[rowx];r[x]=rowx;l[rowx]=x;
}inline void insert_col(int colx, int x)
{d[u[colx]]=x;u[x]=u[colx];d[x]=colx;u[colx]=x;
}void dlx_init(int cols)
{memset(h, -1, sizeof(h));memset(control, 0, sizeof(control));dcnt=-1;addnode(dcnt);for(int i=1;i<=cols;++i){addnode(dcnt);insert_row(0, dcnt);}
}inline void remove(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];control[col[j]]--;}
}inline void resume(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;control[col[j]]++;}l[r[c]]=c;r[l[c]]=c;
}bool DLX(int deep)
{if(r[0]==0){for(int i=0;i<16;i++)puts(str[i]);return true;}int min=M, tempc;for(int i=r[0];i!=0;i=r[i]) if(control[i]<min){min=control[i];tempc=i;}remove(tempc);for(int i=d[tempc];i!=tempc;i=d[i]){str[row[i]/256][row[i]/16%16]=row[i]%16+'A';for(int j=r[i];j!=i;j=r[j]) remove(col[j]);if(DLX(deep+1)) return true;for(int j=l[i];j!=i;j=l[j]) resume(col[j]);}resume(tempc);return false;
}inline void insert_node(int x, int y)
{control[y]++;addnode(dcnt);row[dcnt]=x;col[dcnt]=y;insert_col(y, dcnt);if(h[x]==-1)h[x]=dcnt;elseinsert_row(h[x], dcnt);
}int main()
{
#ifdef ACMfreopen("in.txt", "r", stdin);
#endifwhile(~scanf("%s", str[0])){for(int i=1;i<16;i++) scanf("%s", str[i]);dlx_init(4*16*16);for(int i=1;i<=16;i++) for(int j=1;j<=16;j++){for(int k=1;k<=16;k++) if(str[i-1][j-1]=='-' || str[i-1][j-1]=='A'+(k-1)){int rr=(i-1)*256+(j-1)*16+(k-1);insert_node(rr, 16*16*0+(i-1)*16+k);insert_node(rr, 16*16*1+(j-1)*16+k);insert_node(rr, 16*16*2+(i-1)/4+(j-1)/4*4+(k-1)*16+1);insert_node(rr, 16*16*3+(i-1)*16+j);}}DLX(0);puts("");}
}



HDU 4069

这个模板行必须从1开始，因为没有初始化第0行


//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int N = 9; //3*3Êý¶À
const int MaxN = N*N*N + 10;
const int MaxM = N*N*4 + 10;
const int maxnode = MaxN*4 + MaxM + 10;
char g[MaxN];
int cnt;
struct DLX
{int n,m,size;int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];int H[MaxN],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;size = m;for(int i = 1;i <= n;i++)H[i] = -1;}void Link(int r,int c){++S[Col[++size]=c];Row[size] = r;D[size] = D[c];U[D[c]] = size;U[size] = c;D[c] = size;if(H[r] < 0)H[r] = L[size] = R[size] = size;else{R[size] = R[H[r]];L[R[H[r]]] = size;L[size] = H[r];R[H[r]] = size;}}void remove(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;}void Dance(int d){if(cnt > 1)return;if(R[0] == 0){for(int i = 0;i < d;i++)g[(ans[i]-1)/9] = (ans[i]-1)%9 + '1';cnt++;return;}int c = R[0];for(int i = R[0];i != 0;i = R[i])if(S[i] < S[c])c = i;remove(c);for(int i = D[c];i != c;i = D[i]){ans[d] = Row[i];for(int j = R[i];j != i;j = R[j])remove(Col[j]);Dance(d+1);if(cnt > 1)return;for(int j = L[i];j != i;j = L[j])resume(Col[j]);}resume(c);}
};int id[20][20];
int a[20][20];
void bfs(int sx,int sy,int d)
{queue<pair<int,int> >q;q.push(make_pair(sx,sy));id[sx][sy] = d;while(!q.empty()){pair<int,int> tmp = q.front();int x = tmp.first;int y = tmp.second;q.pop();if(x > 0 && ((a[x][y]%32)/16) == 0)if(id[x-1][y] == -1){id[x-1][y] = d;q.push(make_pair(x-1,y));}if(x < N-1 && ((a[x][y]%128)/64) == 0)if(id[x+1][y] == -1){id[x+1][y] = d;q.push(make_pair(x+1,y));}if(y > 0 && ((a[x][y])/128) == 0)if(id[x][y-1] == -1){id[x][y-1] = d;q.push(make_pair(x,y-1));}if(y < N-1 && ((a[x][y]%64)/32) == 0)if(id[x][y+1] == -1){id[x][y+1] = d;q.push(make_pair(x,y+1));}}
}
DLX dlx;int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T;scanf("%d",&T);int iCase = 0;while(T--){iCase++;for(int i = 0;i < N;i++)for(int j = 0;j < N;j++)scanf("%d",&a[i][j]);memset(id,-1,sizeof(id));int index = 0;for(int i = 0;i < N;i++)for(int j = 0;j < N;j++)if(id[i][j] == -1)bfs(i,j,++index);dlx.init(N*N*N,N*N*4);for(int i = 0;i < N;i++)for(int j = 0;j < N;j++)for(int k = 1;k <= N;k++){if(a[i][j]%16 != 0 && a[i][j]%16 != k)continue;int r = (i*N+j)*N + k;int c1 = i*N+j+1;int c2 = N*N+i*N+k;int c3 = N*N*2+j*N+k;int c4 = N*N*3+(id[i][j]-1)*N+k;dlx.Link(r,c1);dlx.Link(r,c2);dlx.Link(r,c3);dlx.Link(r,c4);}cnt = 0;dlx.Dance(0);printf("Case %d:\n",iCase);if(cnt == 0)printf("No solution\n");else if(cnt > 1)printf("Multiple Solutions\n");else{for(int i = 0;i < N*N;i++){printf("%c",g[i]);if(i % N == N - 1)printf("\n");}}}return 0;
}


这篇关于Dancing links 基础题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

从基础到高级详解Python数值格式化输出的完全指南

从基础到高级详解Python数值格式化输出的完全指南

《从基础到高级详解Python数值格式化输出的完全指南》在数据分析、金融计算和科学报告领域,数值格式化是提升可读性和专业性的关键技术,本文将深入解析Python中数值格式化输出的相关方法,感兴趣的小伙... 目录引言：数值格式化的核心价值一、基础格式化方法1.1 三种核心格式化方式对比1.2 基础格式化示例
阅读更多...
redis-sentinel基础概念及部署流程

redis-sentinel基础概念及部署流程

《redis-sentinel基础概念及部署流程》RedisSentinel是Redis的高可用解决方案,通过监控主从节点、自动故障转移、通知机制及配置提供,实现集群故障恢复与服务持续可用,核心组件包... 目录一. 引言二. 核心功能三. 核心组件四. 故障转移流程五. 服务部署六. sentinel部署
阅读更多...
从基础到进阶详解Python条件判断的实用指南

从基础到进阶详解Python条件判断的实用指南

《从基础到进阶详解Python条件判断的实用指南》本文将通过15个实战案例,带你大家掌握条件判断的核心技巧,并从基础语法到高级应用一网打尽,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录​引言：条件判断为何如此重要一、基础语法：三行代码构建决策系统二、多条件分支：elif的魔法三、
阅读更多...
Python WebSockets 库从基础到实战使用举例

Python WebSockets 库从基础到实战使用举例

《PythonWebSockets库从基础到实战使用举例》WebSocket是一种全双工、持久化的网络通信协议,适用于需要低延迟的应用,如实时聊天、股票行情推送、在线协作、多人游戏等,本文给大家介... 目录1. 引言2. 为什么使用 WebSocket？3. 安装 WebSockets 库4. 使用 We
阅读更多...
从基础到高阶详解Python多态实战应用指南

从基础到高阶详解Python多态实战应用指南

《从基础到高阶详解Python多态实战应用指南》这篇文章主要从基础到高阶为大家详细介绍Python中多态的相关应用与技巧,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、多态的本质：python的“鸭子类型”哲学二、多态的三大实战场景场景1：数据处理管道——统一处理不同数据格式
阅读更多...
MySQL数据类型与表操作全指南( 从基础到高级实践)

MySQL数据类型与表操作全指南( 从基础到高级实践)

《MySQL数据类型与表操作全指南(从基础到高级实践)》本文详解MySQL数据类型分类（数值、日期/时间、字符串）及表操作（创建、修改、维护）,涵盖优化技巧如数据类型选择、备份、分区,强调规范设计与... 目录mysql数据类型详解数值类型日期时间类型字符串类型表操作全解析创建表修改表结构添加列修改列删除列
阅读更多...
Python 函数详解:从基础语法到高级使用技巧

Python 函数详解:从基础语法到高级使用技巧

《Python函数详解:从基础语法到高级使用技巧》本文基于实例代码,全面讲解Python函数的定义、参数传递、变量作用域及类型标注等知识点,帮助初学者快速掌握函数的使用技巧,感兴趣的朋友跟随小编一起... 目录一、函数的基本概念与作用二、函数的定义与调用1. 无参函数2. 带参函数3. 带返回值的函数4.
阅读更多...
python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
从基础到进阶详解Pandas时间数据处理指南

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据
阅读更多...
安装centos8设置基础软件仓库时出错的解决方案

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》：本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2