题目传送门：http://poj.org/problem?id=3074
Dancing_links
#include<iostream>
#include<cstdio>
using namespace std;
char pat[90];
int grid[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,4,4,4,7,7,7},
{0,1,1,1,4,4,4,7,7,7},
{0,1,1,1,4,4,4,7,7,7},
{0,2,2,2,5,5,5,8,8,8},
{0,2,2,2,5,5,5,8,8,8},
{0,2,2,2,5,5,5,8,8,8},
{0,3,3,3,6,6,6,9,9,9},
{0,3,3,3,6,6,6,9,9,9},
{0,3,3,3,6,6,6,9,9,9}
};
namespace Dancing_link{
#define DL Dancing_link
const int MX = 324;
const int N = 1000000;
int rma,cnt,L[N],R[N],U[N],D[N],sz[N],col[N],p[N],v[N];
inline void init(){
rma = 0; cnt = MX;
for (int i=0;i<=MX;i++) L[i] = i-1, R[i] = i+1, U[i] = i, D[i] = i, sz[i] = 0;
L[0] = MX; R[MX] = 0;
}
inline void AddRow(int n, int pos, int val, int *arr){
for (int i=1,w;i<=n;i++) {
w = ++cnt; p[w] = pos; v[w] = val;
col[w] = arr[i]; sz[arr[i]]++;
L[w+1] = w; R[w] = w+1;
D[U[arr[i]]] = w; D[w] = arr[i];
U[w] = U[arr[i]]; U[arr[i]] = w;
}
L[cnt-n+1] = cnt; R[cnt] = cnt-n+1;
}
inline void remove(int w){
L[R[w]] = L[w];
R[L[w]] = R[w];
for (int i=D[w];i!=w && i;i=D[i]) for (int j=R[i];j!=i;j=R[j])
D[U[j]] = D[j], U[D[j]] = U[j], sz[col[j]]--;
}
inline void restore(int w){
for (int i=U[w];i!=w && i;i=U[i]) for (int j=L[i];j!=i;j=L[j])
D[U[j]] = j, U[D[j]] = j, sz[col[j]]++;
L[R[w]] = w;
R[L[w]] = w;
}
bool solve(int d){
if (d == rma+1) return true;
int w = R[0];
for (int i=R[w];i;i=R[i]) if (sz[i] < sz[w]) w = i;
remove(w);
for (int i=D[w];i!=w;i=D[i]) {
pat[p[i]] = v[i]+'0';
for (int j=R[i];j!=i;j=R[j]) remove(col[j]);
if (solve(d+1)) return true;
for (int j=R[i];j!=i;j=R[j]) restore(col[j]);
}
restore(w);
return false;
}
};
inline int ID(int t, int pos, int val) {
return 81*(t-1)+9*(pos-1)+val;
}
inline void build_link(){
static int tmp[10]; DL::init();
for (int j=1,w=1;j<=9;j++) for (int i=1;i<=9;i++,w++) if (pat[w] == '.') {
for (int k=1;k<=9;k++) {
tmp[1] = ID(1,i,k);
tmp[2] = ID(2,j,k);
tmp[3] = ID(3,grid[i][j],k);
tmp[4] = 243+w;
DL::AddRow(4,w,k,tmp);
}
DL::rma++;
}
for (int j=1,w=1;j<=9;j++) for (int i=1;i<=9;i++,w++) if (pat[w] != '.') {
int c = pat[w]-'0';
DL::remove(ID(1,i,c));
DL::remove(ID(2,j,c));
DL::remove(ID(3,grid[i][j],c));
DL::remove(243+w);
}
}
int main(){
while (~scanf("%s",pat+1) && pat[1] != 'e') {
build_link();
if (DL::solve(1)) printf("%s\n",pat+1);
else printf("No solution\n");
}
return 0;
}
This page really has all the information and facts I needed about this subject and
didn’t know who to ask.
This is a really good tip particularly to those fresh to the blogosphere.
Short but very accurate information… Appreciate your sharing this one.
A must read post!
What’s up mates, its great post regarding educationand fully defined, keep it up all the time.
Hello this is kind of of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding experience so I wanted to get guidance from someone with experience.
Any help would be greatly appreciated!
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! By the way, how can we communicate?
My partner and I absolutely love your blog and find almost all of your post’s
to be just what I’m looking for. Does one offer guest
writers to write content for yourself? I wouldn’t mind composing
a post or elaborating on some of the subjects you write related to here.
Again, awesome blog!
Hi there friends, how is everything, and what you desire to say about this paragraph, in my view its genuinely remarkable for me.
Its like you read my mind! You appear to know so much approximately this, such as you wrote the
ebook in it or something. I believe that you just could do with a few %
to drive the message house a little bit, however other than that,
this is excellent blog. An excellent read.
I’ll certainly be back.
What’s up, just wanted to say, I liked this blog post.
It was practical. Keep on posting!
Its like you learn my mind! You appear to understand so much approximately
this, such as you wrote the e-book in it or something. I
think that you can do with a few % to force the message home a bit,
but instead of that, that is excellent blog. A great read.
I’ll certainly be back.
great points altogether, you simply received a
emblem new reader. What could you suggest about your post that you simply made some days ago?
Any certain?
Hmm it seems like your website ate my first comment (it was extremely long) so I
guess I’ll just sum it up what I submitted and say, I’m thoroughly
enjoying your blog. I as well am an aspiring blog writer but I’m still new
to everything. Do you have any suggestions
for newbie blog writers? I’d definitely appreciate it.
Hmm it appears like your blog ate my first comment (it was super
long) so I guess I’ll just sum it up what I had written and
say, I’m thoroughly enjoying your blog. I too am an aspiring blog blogger but
I’m still new to the whole thing. Do you have any suggestions for first-time blog writers?
I’d genuinely appreciate it.
What’s up everybody, here every person is sharing these know-how,
so it’s good to read this blog, and I used to go
to see this webpage everyday.
Definitely imagine that which you said. Your favourite reason appeared to be at the net the
simplest thing to take into accout of. I say to you, I definitely get irked while
other folks think about issues that they plainly do not recognise about.
You managed to hit the nail upon the top and also defined out the entire thing with no need side effect , folks could take
a signal. Will probably be again to get more. Thanks
I loved as much as you will receive carried out right here.
The sketch is attractive, your authored subject matter stylish.
nonetheless, you command get bought an impatience over that you wish be delivering the following.
unwell unquestionably come further formerly again as exactly the same nearly a lot often inside case you shield this hike.
My brother recommended I might like this website. He was entirely right.
This post actually made my day. You cann’t imagine just how much time I had spent
for this info! Thanks!
You should take part in a contest for one of the best websites on the web.
I’m going to recommend this blog!
My spouse and I stumbled over here coming from a different
web address and thought I might check things out.
I like what I see so now i am following you. Look forward
to finding out about your web page repeatedly.
Great work! This is the kind of information that are meant to be shared around the web.
Disgrace on Google for no longer positioning this publish higher!
Come on over and seek advice from my site . Thank you =)
It’s a shame you don’t have a donate button! I’d without a doubt
donate to this brilliant blog! I guess for now i’ll
settle for bookmarking and adding your RSS feed to my Google account.
I look forward to brand new updates and will share this site with my Facebook group.
Chat soon!
I used to be suggested this web site by means of
my cousin. I’m now not positive whether this post is written through him as
no one else know such detailed about my difficulty.
You’re incredible! Thank you!
magnificent publish, very informative. I ponder why the other specialists of this sector
do not understand this. You should proceed your writing. I’m
confident, you’ve a great readers’ base already!
This is my first time pay a visit at here and i am truly pleassant to read all at
alone place.