- 浏览: 118399 次
- 性别:
- 来自: 北京
最新评论
标准数独,精确覆盖
// pku3076.cpp #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl using namespace std; typedef long long LL; const int maxN = 20 * 20 * 20, maxM = 4 * 20 * 20, N = 16, NN = N * N, n = 4; const int max_size = maxN * maxM; const int inf = 0x3f3f3f3f; int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size], RH[max_size]; int S[maxM], O[maxM]; int head, size; int node(int up, int down, int left, int right) { U[size] = up, D[size] = down; L[size] = left, R[size] = right; D[up] = U[down] = R[left] = L[right] = size; return size++; } bool mat[maxN][maxM]; void init(int N, int M) { size = 0; head = node(0, 0, 0, 0); for (int j = 1; j <= M; ++j) { CH[j] = node(size, size, L[head], head), S[j] = 0; } for (int i = 1; i <= N; ++i) { int row = -1, k; for (int j = 1; j <= M; ++j) { if (!mat[i][j]) continue; if (row == -1) { row = node(U[CH[j]], CH[j], size, size); RH[row] = i, CH[row] = CH[j], ++S[j]; } else { k = node(U[CH[j]], CH[j], L[row], row); RH[k] = i, CH[k] = CH[j], ++S[j]; } } } } void remove(const 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[CH[j]]; } } } void resume(const int &c) { for (int i = U[c]; i != c; i = U[i]) { for (int j = L[i]; j != i; j = L[j]) { ++S[CH[j]]; U[D[j]] = D[U[j]] = j; } } L[R[c]] = R[L[c]] = c; } int len; bool dfs(const int &k) { if (R[head] == head) { len = k - 1; return true; } int s = inf, c; for (int t = R[head]; t != head; t = R[t]) { if (S[t] < s) s = S[t], c = t; } remove(c); for (int i = D[c]; i != c; i = D[i]) { O[k] = RH[i]; for (int j = R[i]; j != i; j = R[j]) { remove(CH[j]); } if (dfs(k + 1)) { return true; } for (int j = L[i]; j != i; j = L[j]) { resume(CH[j]); } } resume(c); return false; } char sudoku[20][20]; void make() { memset(mat, false, sizeof(mat)); const int N = 16, NN = N * N, n = 4; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) for (int k = 1; k <= N; ++k) if (sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1) mat[(i - 1) * NN + (j - 1) * N + k][(i - 1) * N + j] = true; for (int i = 1; i <= N; ++i) for (int k = 1; k <= N; ++k) for (int j = 1; j <= N; ++j) if (sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1) mat[(i - 1) * NN + (j - 1) * N + k][NN + (i - 1) * N + k] = true; for (int j = 1; j <= N; ++j) for (int k = 1; k <= N; ++k) for (int i = 1; i <= N; ++i) if (sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1) mat[(i - 1) * NN + (j - 1) * N + k][NN * 2 + (j - 1) * N + k] = true; int region; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) for (int k = 1; k <= N; ++k) { region = ((i - 1) / n) * n + (j - 1) / n + 1; if (sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1) mat[(i - 1) * NN + (j - 1) * N + k][NN * 3 + (region - 1) * N + k] = true; } } int main() { bool first = true; while (scanf("%s", sudoku[1] + 1) != EOF) { for (int i = 2; i <= N; ++i) scanf("%s", sudoku[i] + 1); make(); init(N * N * N, 4 * N * N); dfs(1); for (int i = 1; i <= len; ++i) { int x = (O[i] - 1) / NN + 1; O[i] -= (x - 1) * NN; int y = (O[i] - 1) / N + 1; O[i] -= (y - 1) * N; int z = O[i]; sudoku[x][y] = 'A' + z - 1; } if (first) first = false; else { putchar('\n'); } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) putchar(sudoku[i][j]); putchar('\n'); } } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1151/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 840线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 850线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 887写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 972转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1188封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 798终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1137源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 804import java.util.*; import j ... -
整数划分
2010-10-07 10:38 839#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 980// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1050typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1291Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 775static BufferedReader cin = ... -
DLX hust 1017
2010-08-11 16:50 848“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1039“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1004推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1186/* * Author: rush * Creat ...
相关推荐
DLX Instruction Set Architecture
一款很好用的DLX汇编器,链接器,模拟dlx环境,win7下可视
这是一个用java写得dlx模拟器,实现了流水线和解决相关
DLX CPU VHDL CODE UNIVERSITY
学习使用 DLX 汇编语言编程,进一步分析相关现象。 二、实验设备环境 DLX 汇编语言环境 三、实验内容和要求 自编一段汇编代码,完成一维向量加法运算,并输出结果。观察程序中出现的数据/控 制/结构相关。(注:使用...
dlx语言写的求和运算,计算机系统结构试验
LordPE DLX增强豪华版 (1) 为LordPE查看输入表部分加上搜索功能 (2) 为LordPE查看输入表部分加右键菜单(仅复制ThunkRVA/FirstThunk列). (3) 当点击LordPE查看输入表部分中"View always FirstThunk",保持光条在原来...
DLX指令集实现程序,将汇编代码转换成二进制代码写入文件中。
DLX算法,是由Knuth提出的一种在图论中图遍历的一种高效算法。
用于修改H1、H2步步高学习机内部DLX文件内的图片,从而达到修改学习机内部程序图片显示的效果
DLX用于高效率搜索,是一种覆盖问题模型的算法。DLX利用了双向链表,体现了数据结构的美。
DLX流水线指令调度,测试指令调度对系统性能的影响。包括实验过程,截图,实验原理和改进方法等,供同学们参考。蔡老师的学生你们懂的。
大作业写的MIPS DLX的模拟器 应该是比较好用的。。
(1) 为LordPE查看输入表部分加上搜索功能 (2) 为LordPE查看输入表部分加右键菜单(复制ThunkRVA/FirstThunk列). (3) 当点击LordPE查看输入表部分中"View always FirstThunk",保持光条在原来位置.(LordPE默认会将光条...
windlx模拟器 DLX实验指导书windlx模拟器 DLX实验指导书
DLX处理器浮点数流水线性能的研究.pdf关于DLX的参考文献
A VHDL implementation DLX processor
这些指令既没有出现在Hennessy 和 Patterson的课本中,也没有列在Sailer 和 Kaeli 合编的"The DLX Instruction Set Architecture Handbook"一书中。新的指令是:sgeu, sgtu, sleu, sltu -- all compares using ...
DLX实现,实用Visual C++编程,思想为MIPS体系结构,可以考察系统仿真的性能和指标
懂得不用多介绍了把,下载享用吧