SPOJ 1771 — Yet Another N-Queen Problem (code: NQUEEN)
n皇后问题,其中n<=50,而且棋盘上有一些部分已经放置皇后.
Dancing Links算法搞掉,另外jl大牛似乎用一个改进的DLX算法(貌似是一个十八向的链表…)用极快的速度AC了这道题…
另:C++比Pascal快一倍,真TMD无语…
{
SPOJ 1771; Yet Another N-Queen Problem
- sqybi’s code
- DLX
}
//for my winsty
program nqueen_sqybi;
const
nn = 50;
tt = nn * 6 - 2 + nn * nn * 4;
var
n, i, j, k, temp, tot: longint;
a: array[1..nn]of longint;
col, row, u, d, l, r, size: array[0..tt]of longint;
used: array[1..nn*nn]of boolean;
head: array[1..nn, 1..nn]of longint;
procedure make(x, y: longint);
begin
u[x] := u[y];
d[x] := y;
d[u[y]] := x;
u[y] := x;
inc(size[y]);
col[x] := y;
end;
procedure cover(x: longint);
var
i, j: longint;
begin
if l[r[x]] <> x then exit;
l[r[x]] := l[x];
r[l[x]] := r[x];
i := d[x];
while i <> x do begin
j := r[i];
while j <> i do begin
d[u[j]] := d[j];
u[d[j]] := u[j];
dec(size[col[j]]);
j := r[j];
end;
i := d[i];
end;
end;
procedure recover(x: longint);
var
i, j: longint;
begin
i := u[x];
while i <> x do begin
j := l[i];
while j <> i do begin
d[u[j]] := j;
u[d[j]] := j;
inc(size[col[j]]);
j := l[j];
end;
i := u[i];
end;
l[r[x]] := x;
r[l[x]] := x;
end;
function dfs(x: longint): boolean;
var
temp, temp_, min: longint;
begin
dfs := true;
if x > n then exit;
dfs := false;
min := 0;
temp := r[0];
while temp <= n * 2 do begin
if (min = 0) or (size[temp] < size[min]) then
min := temp;
temp := r[temp];
end;
if size[min] = 0 then exit;
cover(min);
temp := d[min];
while temp <> min do begin
temp_ := r[temp];
while temp_ <> temp do begin
cover(col[temp_]);
temp_ := r[temp_];
end;
used[row[temp]] := true;
if dfs(x+1) then begin
dfs := true;
exit;
end;
used[row[temp]] := false;
temp_ := l[temp];
while temp_ <> temp do begin
recover(col[temp_]);
temp_ := l[temp_];
end;
temp := d[temp];
end;
recover(min);
end;
begin
while not eof do begin
read(n);
for i:=1 to n do read(a[i]);
readln;
for i:=0 to n*6-2 do begin
if i = 0 then
l[i] := n * 6 - 2
else
l[i] := i - 1;
if i = n * 6 - 2 then
r[i] := 0
else
r[i] := i + 1;
u[i] := i;
d[i] := i;
size[i] := 0;
end;
tot := n * 6 - 2;
for i:=1 to n do
for j:=1 to n do begin
for k:=1 to 4 do begin
if k = 1 then
l[tot+k] := tot + 4
else
l[tot+k] := tot + k - 1;
if k = 4 then
r[tot+k] := tot + 1
else
r[tot+k] := tot + k + 1;
row[tot+k] := (i - 1) * n + j;
end;
make(tot+1, i);
make(tot+2, n+j);
make(tot+3, n*2+i+j-1);
make(tot+4, n*5-1+i-j);
head[i, j] := tot + 1;
tot := tot + 4;
end;
k := 0;
for i:=1 to n do
if a[i] <> 0 then begin
temp := head[i, a[i]];
repeat
cover(col[temp]);
temp := r[temp];
until temp = head[i, a[i]];
inc(k);
end;
fillchar(used, sizeof(used), false);
dfs(k+1);
for i:=1 to n do
for j:=1 to n do
if used[(i-1)*n+j] then
a[i] := j;
for i:=1 to n do write(a[i], ‘ ‘);
writeln;
end;
end.
阅读(156 次)