67 条题解
-
2
sonicmisora LV 8 @ 2009-09-17 17:32:48
数独最权威最快的算法还是DANCING LINKS X吧，的确挺快的，绝大部分数据都是秒杀。
-
1
#include<cstdio>
#include<cstring>
int n,a[10][10];
char s[100];
bool h[10][10],l[10][10],sq[10][10];void Print();
void DFS(int x,int y);
int Getsq(int x,int y);int main(){
freopen("p1345.in","r",stdin);
scanf("%d",&n);
for (int k=1;k<=n;k++){
memset(h,false,sizeof h);
memset(l,false,sizeof l);
memset(sq,false,sizeof sq);
scanf("%s",s);
for (int i=1;i<=9;i++){
for (int j=1;j<=9;j++) a[i][j]=s[(i-1)*9+j-1]-'0',h[i][a[i][j]]=l[j][a[i][j]]=true,sq[Getsq(i,j)][a[i][j]]=true;
}
DFS(1,1);
}
}void DFS(int x,int y){
if (a[x][y]!=0){
if (x==9 && y==9) Print();
else if (y==9) DFS(x+1,1);
else DFS(x,y+1);
}
else
for (int num=1;num<=9;num++){
if (!sq[Getsq(x,y)][num] && !h[x][num] && !l[y][num]){
sq[Getsq(x,y)][num]=h[x][num]=l[y][num]=true;
a[x][y]=num;
if (x==9 && y==9) Print();
else if (y==9) DFS(x+1,1);
else DFS(x,y+1);
a[x][y]=0;
sq[Getsq(x,y)][num]=h[x][num]=l[y][num]=false;
}
}
}int Getsq(int x,int y){
return (((x-1)/3)*3+(y-1)/3+1);
}void Print(){
for (int i=1;i<=9;i++){
for (int j=1;j<=9;j++) printf("%d",a[i][j]);
}
printf("\n");
}why WA? 求大神指点...
-
0
不知道哪里错了，帮我看一下程序，谢谢
编译通过...
├ 测试数据 01：运行超时|格式错误...
├ 测试数据 02：答案错误...
├ Hint: 程序问题多了。 ├ 标准行输出
├ 错误行输出├ 测试数据 03：答案错误...
├ Hint: 稍变态。 ├ 标准行输出
├ 错误行输出├ 测试数据 04：运行超时...
├ 测试数据 05：运行超时...
├ 测试数据 06：运行超时|格式错误...
├ 测试数据 07：运行超时...
├ 测试数据 08：答案错误...
├ Hint: 垃圾点。 ├ 标准行输出
├ 错误行输出├ 测试数据 09：运行超时...
├ 测试数据 10：答案错误...
├ Hint: 极变态，过不了也没什么。 ├ 标准行输出
├ 错误行输出---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：0 有效耗时：0mstype r=array[1..9,1..9] of byte;
var f:array[1..9,1..9,1..9,1..2] of integer;
n,i,j,k:integer;
ch:char;
a:r;
procedure search(x,y:integer);
var ii,jj:integer;
bool:boolean;
begin
if (x=9) and (y=9) then begin
for ii:=1 to 9 do
for jj:=1 to 9 do
write(a[ii,jj]);
writeln;
exit;
end else begin
inc(y);
if y=10 then begin x:=x+1; y:=1; end;
if a[x,y]0 then search(x,y) else begin
for ii:=1 to 9 do begin
bool:=true;
for jj:=1 to 9 do
if ii=a[f[x,y,jj,1],f[x,y,jj,2]] then bool:=false;
if bool=true then begin
for jj:=1 to 9 do
if (a[x,jj]=ii) or (a[jj,y]=ii) then bool:=false;
if bool=true then begin
a[x,y]:=ii;
search(x,y);
a[x,y]:=0;
end;
end;
end;
end;
end;
end;begin
readln(n);
for i:=1 to 3 do
for j:=1 to 3 do begin
f:=1; f:=1; f:=1;
f:=1; f:=2; f:=3;
f:=2; f:=2; f:=2;
f:=1; f:=2; f:=3;
f:=3; f:=3; f:=3;
f:=1; f:=2; f:=3;
end;
for i:=1 to 3 do
for j:=4 to 6 do begin
f:=1; f:=1; f:=1;
f:=4; f:=5; f:=6;
f:=2; f:=2; f:=2;
f:=4; f:=5; f:=6;
f:=3; f:=3; f:=3;
f:=4; f:=5; f:=6;
end;
for i:=1 to 3 do
for j:=7 to 9 do begin
f:=1; f:=1; f:=1;
f:=7; f:=8; f:=9;
f:=2; f:=2; f:=2;
f:=7; f:=8; f:=9;
f:=3; f:=3; f:=3;
f:=7; f:=8; f:=9;
end;
for i:=4 to 6 do
for j:=1 to 3 do begin
f:=4; f:=5; f:=6;
f:=1; f:=2; f:=3;
f:=4; f:=5; f:=6;
f:=1; f:=2; f:=3;
f:=4; f:=5; f:=6;
f:=1; f:=2; f:=3;
end;
for i:=4 to 6 do
for j:=4 to 6 do begin
f:=4; f:=4; f:=4;
f:=4; f:=5; f:=6;
f:=5; f:=5; f:=5;
f:=4; f:=5; f:=6;
f:=6; f:=6; f:=6;
f:=4; f:=5; f:=6;
end;
for i:=4 to 6 do
for j:=7 to 9 do begin
f:=4; f:=4; f:=4;
f:=7; f:=8; f:=9;
f:=5; f:=5; f:=5;
f:=7; f:=8; f:=9;
f:=6; f:=6; f:=6;
f:=7; f:=8; f:=9;
end;
for i:=7 to 9 do
for j:=1 to 3 do begin
f:=7; f:=7; f:=7;
f:=1; f:=2; f:=3;
f:=8; f:=8; f:=8;
f:=1; f:=2; f:=3;
f:=9; f:=9; f:=9;
f:=1; f:=2; f:=3;
end;
for i:=7 to 9 do
for j:=4 to 6 do begin
f:=7; f:=7; f:=7;
f:=4; f:=5; f:=6;
f:=8; f:=8; f:=8;
f:=4; f:=5; f:=6;
f:=9; f:=9; f:=9;
f:=4; f:=5; f:=6;
end;
for i:=7 to 9 do
for j:=7 to 9 do begin
f:=7; f:=7; f:=7;
f:=7; f:=8; f:=9;
f:=8; f:=8; f:=8;
f:=7; f:=8; f:=9;
f:=9; f:=9; f:=9;
f:=7; f:=8; f:=9;
end;
for i:=1 to n do begin
fillchar(a,sizeof(a),0);
for j:=1 to 9 do
for k:=1 to 9 do begin
read(ch);
a[j,k]:=ord(ch)-48;
end;
search(0,9);
end;
end.虽然有点长，但容易理解，谢谢
-
0
编译通过...
├ 测试数据 01：答案正确... 1541ms
├ 测试数据 02：答案正确... 150ms
├ 测试数据 03：答案正确... 744ms
├ 测试数据 04：答案正确... 291ms
├ 测试数据 05：答案正确... 7619ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 681ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 306ms
├ 测试数据 10：答案正确... 1416ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：12748ms
过了我几乎两天！！！搜索是在写得太丑了！！！交了近20次！！！悲哀ing！！！
爆搜确实能过！但只要有一个地方想差了，你就别想过了！下面是我认为最核心的部分！
const int MAXN=10;
int jgg[MAXN][MAXN]=
{{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9}};
struct point
{
int x,y;
};
point wwg[82];
int num;
int a[MAXN][MAXN];
bool h[MAXN][MAXN],l[MAXN][MAXN],pj[MAXN][MAXN];
如果没有把这些定义好的话！我想一定会超！特别是jgg【】【】这个数组！！！太重要了！！！！
然后就是这个
if(pj[jgg[wwg[m].x][wwg[m].y]][i]==false)
if(h[wwg[m].x][i]==false)
if(l[wwg[m].y][i]==false)
这三个判断的顺序是关键！！！
改了顺序就能过变态的第五组数据啦！
虽说是搜索，细节决定成败！！！ -
0
编译通过...
├ 测试数据 01：答案正确... 103ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 134ms
├ 测试数据 04：答案正确... 9ms
├ 测试数据 05：答案正确... 275ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 447ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：968ms -
0
编译通过...
├ 测试数据 01：答案正确... 1244ms
├ 测试数据 02：答案正确... 134ms
├ 测试数据 03：答案正确... 634ms
├ 测试数据 04：答案正确... 212ms
├ 测试数据 05：答案正确... 5947ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 666ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 291ms
├ 测试数据 10：答案正确... 1322ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：10450ms
部分评测机会挂
核心部分：
int search(int i,int j)
{
if(table[i][j]>0)
{
if(i==8&&j==8)
return 1;
int result;
if(j==8)
result=search(i+1,0);
else
result=search(i,j+1);
return result;
}
else
{
for(int cur=1;cur -
0
编译通过...
├ 测试数据 01：答案正确... 2212ms
├ 测试数据 02：答案正确... 478ms
├ 测试数据 03：答案正确... 619ms
├ 测试数据 04：答案正确... 72ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 775ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 666ms
├ 测试数据 10：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：4894ms按列搜索很快啊
-
0
我用的深搜，不过时间上有点囧。
第一次，搜索顺序先行后列（即1,1-->1,9-->2,1-->……-->9,9）：
编译通过...
├ 测试数据 01：答案正确... 1603ms
├ 测试数据 02：答案正确... 181ms
├ 测试数据 03：答案正确... 853ms
├ 测试数据 04：答案正确... 306ms
├ 测试数据 05：运行超时|无输出...
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：运行超时...
├ 测试数据 08：答案正确... 9ms
├ 测试数据 09：答案正确... 400ms
├ 测试数据 10：答案正确... 1556ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：75 有效耗时：4908ms第二次，搜索顺序先列后行（即1,1-->9,1-->1,2-->……-->9,9）：编译通过...
├ 测试数据 01：答案正确... 2181ms
├ 测试数据 02：答案正确... 462ms
├ 测试数据 03：答案正确... 634ms
├ 测试数据 04：答案正确... 72ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 759ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 728ms
├ 测试数据 10：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：4924ms我最感兴趣的是第一次提交时，我只错了两个点，却扣了25分？有意思。
-
0
编译通过...
├ 测试数据 01：答案正确... 2119ms
├ 测试数据 02：答案正确... 478ms
├ 测试数据 03：答案正确... 634ms
├ 测试数据 04：答案正确... 56ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 791ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 712ms
├ 测试数据 10：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：4878ms膜拜秒杀的大牛！！！
-
0
fammiebright LV 9 @ 2009-07-28 18:41:19
编译通过...
├ 测试数据 01：答案正确... 1447ms
├ 测试数据 02：答案正确... 119ms
├ 测试数据 03：答案正确... 775ms
├ 测试数据 04：答案正确... 259ms
├ 测试数据 05：答案正确... 6822ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 759ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 338ms
├ 测试数据 10：答案正确... 1400ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：11919m纯朴素dfs。
-
0
NaTuReHugh LV 9 @ 2009-07-24 12:14:33
编译通过...
├ 测试数据 01：答案正确... 1056ms
├ 测试数据 02：答案正确... 88ms
├ 测试数据 03：答案正确... 572ms
├ 测试数据 04：答案正确... 150ms
├ 测试数据 05：答案正确... 712ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 197ms
├ 测试数据 09：答案正确... 572ms
├ 测试数据 10：答案正确... 103ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：3450ms正着搜索95分，倒着95分，最后干脆根据N尽心随即正反，就AC了，汗
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms数据不是什么骨灰数据，否则一个数据我的方法就可能跑超过500ms。
数据全部是简单数据，根本不用DLX
sonicmisora
LV 8
@ 2009-09-17 17:32:48
