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。

相关文章

零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
【Linux 从基础到进阶】Ansible自动化运维工具使用

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具，采用无代理架构（agentless），基于 SSH 连接进行管理，具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用，旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
c++基础版

c++基础版

c++基础版 Windows环境搭建第一个C++程序c++程序运行原理注释常亮字面常亮符号常亮 变量数据类型整型实型常量类型确定char类型字符串布尔类型 控制台输入随机数产生枚举定义数组数组便利 指针基础野指针空指针指针运算动态内存分配 结构体结构体默认值结构体数组结构体指针结构体指针数组函数无返回值函数和void类型地址传递函数传递数组 引用函数引用传参返回指针的正确写法函数返回数组
阅读更多...
【QT】基础入门学习

【QT】基础入门学习

文章目录 浅析Qt应用程序的主函数使用qDebug()函数常用快捷键Qt 编码风格信号槽连接模型实现方案 信号和槽的工作机制Qt对象树机制 浅析Qt应用程序的主函数 #include "mywindow.h"#include <QApplication>// 程序的入口int main(int argc, char *argv[]){// argc是命令行参数个数，argv是
阅读更多...
【MRI基础】TR 和 TE 时间概念

【MRI基础】TR 和 TE 时间概念

重复时间 (TR) 磁共振成像 (MRI) 中的 TR（重复时间，repetition time）是施加于同一切片的连续脉冲序列之间的时间间隔。具体而言，TR 是施加一个 RF（射频）脉冲与施加下一个 RF 脉冲之间的持续时间。TR 以毫秒 (ms) 为单位，主要控制后续脉冲之前的纵向弛豫程度（T1 弛豫），使其成为显著影响 MRI 中的图像对比度和信号特性的重要参数。 回声时间 (TE)
阅读更多...
Java基础回顾系列-第七天-高级编程之IO

Java基础回顾系列-第七天-高级编程之IO

Java基础回顾系列-第七天-高级编程之IO 文件操作字节流与字符流OutputStream字节输出流FileOutputStream InputStream字节输入流FileInputStream Writer字符输出流FileWriter Reader字符输入流字节流与字符流的区别转换流InputStreamReaderOutputStreamWriter 文件复制 字符编码内存操作流(
阅读更多...
Java基础回顾系列-第五天-高级编程之API类库

Java基础回顾系列-第五天-高级编程之API类库

Java基础回顾系列-第五天-高级编程之API类库 Java基础类库StringBufferStringBuilderStringCharSequence接口AutoCloseable接口RuntimeSystemCleaner对象克隆 数字操作类Math数学计算类Random随机数生成类BigInteger/BigDecimal大数字操作类 日期操作类DateSimpleDateForma
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2