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操作redis基础

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对（Key-Value）存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re
阅读更多...
SpringBoot基础框架详解

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2
阅读更多...
Spring Boot集成SLF4j从基础到高级实践(最新推荐)

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面（Facade）,不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4
阅读更多...
Spring Boot集成Logback终极指南之从基础到高级配置实战指南

Spring Boot集成Logback终极指南之从基础到高级配置实战指南

《SpringBoot集成Logback终极指南之从基础到高级配置实战指南》Logback是一个可靠、通用且快速的Java日志框架,作为Log4j的继承者,由Log4j创始人设计,：本文主要介绍... 目录一、Logback简介与Spring Boot集成基础1.1 Logback是什么？1.2 Sprin
阅读更多...
MySQL复合查询从基础到多表关联与高级技巧全解析

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言：1.基本查询回顾：1.1.查询工资高于500或岗位为MANAGER的雇员，同时还要满足他们的姓名首字母为大写的J1.2.按照部门
阅读更多...
Android Mainline基础简介

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline？Android Mainline 的工作原理关键
阅读更多...
mysql的基础语句和外键查询及其语句详解(推荐)

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》：本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键
阅读更多...
Python基础语法中defaultdict的使用小结

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典（dict）有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字
阅读更多...
Python基础文件操作方法超详细讲解(详解版)

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,：本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.
阅读更多...
C#基础之委托详解(Delegate)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》：本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托（Multicast Delegates）4. 委托的用途事件处理回调函数LINQ
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2