17 条题解
-
5
lyyyzx LV 10 @ 2016-11-12 16:59:57
最近学了**DLX算法**，中文叫舞蹈链，英文叫**Dancing Links**，用于精确覆盖模型 ，问题描述为：
在01矩阵中，选定最少的行，使得每列有且仅有一个1.由于Dancing Links 用双向十字链表存储稀疏矩阵，**效率极高**,我最慢的一个点为171ms。
对于 元素为1~N 的数独 ，我们可以构造 N*N*N 行 因为一共有N*N*N小格，每个小格有N个可能性，每一种可能性对应这一行。列则有（N+N+N）*N+N*N 列 其中前面3个N分别表示N行、N列、N小块，乘N表示有N中可能，每种可能只能选一个。N*N表示N*N个小格，限制每个小格只可以放一个地方。
然后直接调用模版就可以了
时间复杂度极其低对于Dancing Links的数据结构及原理网上有，我只说一下怎样建图。
附上C++代码：#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define maxn 1010 #define maxnode maxn*maxn int W[9][9]={ { 6,6,6,6,6,6,6,6,6 }, { 6,7,7,7,7,7,7,7,6 }, { 6,7,8,8,8,8,8,7,6 }, { 6,7,8,9,9,9,8,7,6 }, { 6,7,8,9,10,9,8,7,6 }, { 6,7,8,9,9,9,8,7,6 }, { 6,7,8,8,8,8,8,7,6 }, { 6,7,7,7,7,7,7,7,6 }, { 6,6,6,6,6,6,6,6,6 } }; bool flag=false; struct DLX { int n, m, index, head, ansk;//列 int S[maxn], ans[maxnode]; //每列的个数 int row[maxnode], col[maxnode]; int L[maxnode], R[maxnode], U[maxnode], D[maxnode], H[maxnode]; void link(int r, int c) {//行，列 插入循序从左到右 从上到下 S[c]++; row[index] = r; col[index] = c; U[index] = U[c]; D[U[c]] = index; D[index] = c; U[c] = index; if( H[r]==-1 ) H[r] = L[index] = R[index] = index; else { L[index] = L[H[r]]; R[index] = H[r]; R[L[H[r]]] = index; L[H[r]] = index; } index++; } void init() { int i; head=0; for( i=head;i<=m ;i++ ) { R[i]= (i+1)%(m+1); L[i]= (i-1+m+1)%(m+1); U[i]=D[i]=i; } memset(H,-1,sizeof(H)); memset(S,0,sizeof(S)); index = m+1; } #define FOR(i,A,k) for(int i=A[k]; i!=k; i=A[i] ) void remove(int c){ L[R[c]] = L[c]; R[L[c]] = R[c]; FOR( i, D, c ) FOR( j, R, i ) { U[D[j]] = U[j]; D[U[j]] = D[j]; S[col[j]]--; } } void restore(int c){ FOR( i, U, c ) FOR( j, L, i ) { ++S[col[j]]; U[D[j]] = j; D[U[j]] = j; } L[R[c]] = c; R[L[c]] = c; } bool dfs(int k) { if( R[head]==head ) { //do something flag=true; int cnt=0; for( int j=0;j<k;j++ ) { int i=ans[j]; cnt+= W[chess[i].x][chess[i].y] * chess[i].w; } if( cnt > ansk ) ansk=cnt; //cout<<cnt<<endl; return true; } int c=R[head]; FOR(i,R,head) if( S[i]<S[c] ) c=i; remove(c); FOR(i,D,c) { ans[k]=row[i]; FOR(j,R,i) remove(col[j]); dfs( k+1 ); FOR(j,L,i) restore(col[j]); } restore(c); return false; } //舞蹈链模版结束 //---------------------------------------------------------------------- struct Piece { int x,y,w; }; Piece chess[maxn]; void slove() { int i,j,tmp,s,t; m=(9+9+9)*9+9*9;// n行n列n小块*n种状态+n*n个位置 n=0; ansk=0; init(); for( i=0;i<9;i++) for( j=0;j<9;j++ ) { cin>>tmp; if( tmp ) s=tmp,t=tmp; //如果有值就只插入一排 else s=1,t=9;//其他就插入9种情况 while(s<=t) { n++; chess[n].x=i; chess[n].y=j; chess[n].w=s; link( n, i*9+s );//行 link( n, 9*9+j*9+s );//列 link( n, 2*9*9+( (i/3)*3+j/3 )*9+s ); //块 link( n, 3*9*9+ i*9+j+1 ) ;////每个格子 s++; } } dfs(0); if( flag ) printf("%d\n",ansk); else printf("-1\n"); } //我就只打了这么点，横线上面全是模版，只是稍微改了下更新结果的地方 //-------------------------------------------------------------------------- }; DLX T; int main() { //freopen("in.txt","r",stdin); //T.slove_HUST_1017(); T.slove(); return 0; } -
1
3g93zhmq (3g93zhmq) LV 8 @ 2019-05-27 14:46:47
#include<iostream> #include<algorithm> using namespace std; struct f { int rank,sum;//定义结构体，将行号与0的个数对应 }cou[10]; int a[10][10],hang[10][10],lie[10][10],gong[10][10],s[100][4],u,ok,most=-1,have; int which(int,int);//给出两个整型变量代表坐标，返回此坐标的所在宫 int point(int,int);//给出两个整型变量代表坐标，返回此坐标的分值 void dfs(int,int); bool cmp(f a,f b) { return a.sum<b.sum; } int main() { for(int i=1;i<=9;i++) cou[i].rank=i;//rank存其初始行号，排序后就不会丢失 for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { cin>>a[i][j]; if(a[i][j]>0) hang[i][a[i][j]]=lie[j][a[i][j]]=gong[which(i,j)][a[i][j]]=1,have+=a[i][j]*point(i,j);//非零就不存储到搜索数组s中，但将这个点的值在其所在行、列、宫中标记 ，计算加分 else cou[i].sum++;//是0就计数 } sort(cou+1,cou+10,cmp);//排序，0少的在前 for(int i=1;i<=9;i++)//整理s数组，准备搜索 { for(int j=1;j<=9;j++)//先搜0少的行 if(a[cou[i].rank][j]==0) s[u][0]=cou[i].rank,s[u][1]=j,s[u][2]=point(cou[i].rank,j),s[u++][3]=which(cou[i].rank,j);//保存不解释 } dfs(0,have);//搜索 cout<<most<<endl;//most保存答案，初始值为-1 return 0; } void dfs(int p,int score)// 表示正在搜s[p],score为目前分数 { if(p==u)//合法填完了所有的数 { if(score>most) most=score;//更大就更新 return; } for(int i=1;i<=9;i++) { if(!hang[s[p][0]][i]&&!lie[s[p][1]][i]&&!gong[s[p][3]][i])//判断可不可以将i填入 { hang[s[p][0]][i]=lie[s[p][1]][i]=gong[s[p][3]][i]=1;//填了后就将这个点的值在其所在行、列、宫中标记 dfs(p+1,score+(s[p][2]*i));//下一层递归 hang[s[p][0]][i]=lie[s[p][1]][i]=gong[s[p][3]][i]=0;//回溯 } } return; } int which(int i,int j) { if(i<=3) { if(j<=3) return 1; else if(j<=6) return 2; else return 3; } else if(i<=6) { if(j<=3) return 4; else if(j<=6) return 5; else return 6; } else { if(j<=3) return 7; else if(j<=6) return 8; else return 9; } } int point(int i,int j) { if(i==1||j==1||i==9||j==9) return 6; if(i==2||j==2||i==8||j==8) return 7; if(i==3||j==3||i==7||j==7) return 8; if(i==4||j==4||i==6||j==6) return 9; return 10; } -
1
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
int getint(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f; ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return f*x;
}
const int MAXN=12;
const int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
int row[MAXN][MAXN],col[MAXN][MAXN],area[MAXN][MAXN],sdk[MAXN][MAXN];
int row_cnt[MAXN],col_cnt[MAXN],cnt,ans=-1;
inline int id(int i,int j){return (i-1)/3*3+1+(j-1)/3;}
inline int calc(){
int tmp=0;
for(int i=1;i<=9;++i)
for(int j=1;j<=9;++j)
tmp+=score[i][j]*sdk[i][j];
return tmp;
}
void dfs(int r,int c,int cpl){
if(cpl==81){
ans=max(ans,calc());
return ;
}
for(int k=1;k<=9;++k){
if(row[r][k]||col[c][k]||area[id(r,c)][k]) continue;
row[r][k]=true;
col[c][k]=true;
area[id(r,c)][k]=true;
row_cnt[r]++,col_cnt[c]++;
sdk[r][c]=k;
int tmpr=-1,nxt_r=0,tmpc=-1,nxt_c=0;
for(int i=1;i<=9;++i)
if(row_cnt[i]>tmpr&&row_cnt[i]<9)
tmpr=row_cnt[i],nxt_r=i;
for(int j=1;j<=9;++j)
if(col_cnt[j]>tmpc&&(!sdk[nxt_r][j]))
tmpc=col_cnt[j],nxt_c=j;
dfs(nxt_r,nxt_c,cpl+1);
row[r][k]=false;
col[c][k]=false;
area[id(r,c)][k]=false;
row_cnt[r]--,col_cnt[c]--;
sdk[r][c]=0;
}
}
int main(){
for(int i=1;i<=9;++i){
for(int j=1;j<=9;++j){
sdk[i][j]=getint();
if(sdk[i][j]!=0){
row[i][sdk[i][j]]=true;
col[j][sdk[i][j]]=true;
area[id(i,j)][sdk[i][j]]=true;
row_cnt[i]++,col_cnt[j]++;
cnt++;
}
}
}
int tmpr=-1,r,tmpc=-1,c;
for(int i=1;i<=9;++i)
if(row_cnt[i]>tmpr&&row_cnt[i]<9)
tmpr=row_cnt[i],r=i;
for(int j=1;j<=9;++j)
if(col_cnt[j]>tmpc&&(!sdk[r][j]))
tmpc=col_cnt[j],c=j;
dfs(r,c,cnt);
cout<<ans<<endl;
} -
0
静态调整搜索序 + 二进制压位
跑得过普通搜索 但跑不过DLX。。#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> const int maxn = 9 + 10; const int scr[9][9] = {{6, 6, 6, 6, 6, 6, 6, 6, 6}, {6, 7, 7, 7, 7, 7, 7, 7, 6}, {6, 7, 8, 8, 8, 8, 8, 7, 6}, {6, 7, 8, 9, 9, 9, 8, 7, 6}, {6, 7, 8, 9, 10, 9, 8, 7, 6}, {6, 7, 8, 9, 9, 9, 8, 7, 6}, {6, 7, 8, 8, 8, 8, 8, 7, 6}, {6, 7, 7, 7, 7, 7, 7, 7, 6}, {6, 6, 6, 6, 6, 6, 6, 6, 6}}; const int fsq[9][9] = {{0, 0, 0, 1, 1, 1, 2, 2, 2}, {0, 0, 0, 1, 1, 1, 2, 2, 2}, {0, 0, 0, 1, 1, 1, 2, 2, 2}, {3, 3, 3, 4, 4, 4, 5, 5, 5}, {3, 3, 3, 4, 4, 4, 5, 5, 5}, {3, 3, 3, 4, 4, 4, 5, 5, 5}, {6, 6, 6, 7, 7, 7, 8, 8, 8}, {6, 6, 6, 7, 7, 7, 8, 8, 8}, {6, 6, 6, 7, 7, 7, 8, 8, 8}}; int ln[maxn], rw[maxn], sq[maxn], ans[maxn][maxn], score = -1; struct Line { int val, id; }ord[maxn]; bool cmp(const Line& a, const Line& b) { return a.val > b.val; } void work() { int k = 0; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) k += ans[i][j] * scr[i][j]; score = std::max(score, k); return; } void dfs(int k, int y) { if (k == 9) { work(); return; } if (y == 9) { dfs(k + 1, 0); } else if (!ans[ord[k].id][y]) { int x = ord[k].id; for (int i = 0; i < 9; i++) if (!(ln[x] & (1 << i)) && !(rw[y] & (1 << i)) && !(sq[fsq[x][y]] & (1 << i))) { ln[x] |= 1 << i; rw[y] |= 1 << i; sq[fsq[x][y]] |= 1 << i; ans[x][y] = i + 1; #ifdef DEBUG printf("%d %d\n", x, y); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) printf("%d ", ans[i][j]); puts(""); } puts(""); #endif dfs(k, y + 1); ln[x] = ln[x] ^ (1 << i); rw[y] = rw[y] ^ (1 << i); sq[fsq[x][y]] = sq[fsq[x][y]] ^ (1 << i); ans[x][y] = 0; } } else { dfs(k, y + 1); } return; } int main() { memset(ln, 0, sizeof ln); memset(rw, 0, sizeof rw); memset(sq, 0, sizeof sq); memset(ord, 0, sizeof ord); for (int i = 0; i < 9; i++) { int now = 0; for (int j = 0; j < 9; j++) { scanf("%d", &ans[i][j]); if (ans[i][j]) { int a = ans[i][j] - 1; now++; ln[i] |= 1 << a; rw[j] |= 1 << a; sq[fsq[i][j]] |= 1 << a; } } ord[i].val = now; ord[i].id = i; } std::sort(ord, ord + 9, cmp); dfs(0,0); printf("%d\n", score); return 0; } -
0
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int s[10][10]={
{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},
}; //这是每个九宫格的预处理。
const int p[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}
}; //分值
bool line[10][10],row[10][10],square[10][10],check[10][10];
int xx,yy,n,num,i,j,ans,k,m,now,last,cnt,a[10][10],f[10][10]; //f就是限制
struct arr
{
int x;
int y;
}order[100]; //order是枚举顺序。
inline void get_square(int i,int j) //找到当前i,j的九宫格的左上角
{
if (i<=3) xx=1;
else if (i<=6) xx=4;
else xx=7;
if (j<=3) yy=1;
else if (j<=6) yy=4;
else yy=7;
}
inline void get_order(int k) //每次寻找限制第k多的0的位置
{
int max=0,x,y,i,j;
for (i=1;i<=9;i++)
for (j=1;j<=9;j++)
if (check[i][j]&&f[i][j]>max)
{
max=f[i][j];
x=i;
y=j;
}
order[k].x=x;
order[k].y=y;
for (i=1;i<=9;i++)
{
f[i][y]++;
f[x][i]++;
}
get_square(x,y);
for (i=xx;i<=xx+2;i++)
for (j=yy;j<=yy+2;j++)
f[i][j]++;
check[x][y]=false;
}
inline void dfs(int k) //容易理解的dfs
{
if (k==num+1)
{
if (now>ans) ans=now;
return;
}
int x=order[k].x;
int y=order[k].y;
for (int i=1;i<=9;i++)
if (line[x][i]&&row[y][i]&&square[s[x][y]][i])
{
now+=i*p[x][y];
line[x][i]=false;
row[y][i]=false;
square[s[x][y]][i]=false;
dfs(k+1);
now-=i*p[x][y];
line[x][i]=true;
row[y][i]=true;
square[s[x][y]][i]=true;
}
}
int main()
{
memset(line,1,sizeof(line));
memset(row,1,sizeof(row));
memset(square,1,sizeof(square));
for (i=1;i<=9;i++)
for (j=1;j<=9;j++)
{
scanf("%ld",&a[i][j]);
if (a[i][j]>0)
{
line[i][a[i][j]]=false;
row[j][a[i][j]]=false;
square[s[i][j]][a[i][j]]=false;
last+=a[i][j]*p[i][j]; //原来已经填好的分值
for (k=1;k<=9;k++)
{
f[i][k]++;f[k][j]++;
}
get_square(i,j);
for (k=xx;k<=xx+2;k++)
for (m=yy;m<=yy+2;m++)
f[k][m]++;
}
else
{
num++;
check[i][j]=true;
}
}
for (i=1;i<=num;i++) get_order(i);
ans=-1;dfs(1);
if (ans==-1)
last=0;
printf("%d\n",ans+last);
return 0;
} -
0
和大家写的其实都差不多，但是要注意其实是可以加上_可行性剪枝_的，说白了就是先扫一遍每个空格能选几个数，不能出现一个不能选或者冲突的情况
```c++
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int mp[10][10];
const int grade[10][10] = {
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}
};const int belong[10][10] = {
{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}
};
int ans;bool vis_Line[10][10],vis_Row[10][10],vis_sq[10][10];
void show()
{
for(int i=1;i<=9;++i)
{
for(int j=1;j<=9;++j)
cout << mp[i][j] << " ";
puts("");
}
}int calc()
{
// show();
int tmp = 0;
for(int i=1;i<=9;++i)
for(int j=1;j<=9;++j)
tmp += mp[i][j] * grade[i][j];
return tmp;
}void DFS()
{
int tmp = 10;
int tmpi,tmpj;
for(int i=1;i<=9;++i)
for(int j=1;j<=9;++j)
if(!mp[i][j])
{
int cnt = 0;
for(int k=1;k<=9;++k)
if(!vis_Line[i][k] && !vis_Row[j][k] && !vis_sq[belong[i][j]][k])
cnt++;
if(!mp[i][j] && cnt == 0) return;
if(cnt <= tmp)
tmpi = i , tmpj = j,tmp = cnt;
}if(tmp == 10)
{
ans = max(ans,calc());
return ;
}
for(int k=1;k<=9;++k)
{
if(!vis_Line[tmpi][k] && !vis_Row[tmpj][k] && !vis_sq[belong[tmpi][tmpj]][k])
{
vis_Line[tmpi][k] = vis_Row[tmpj][k] = vis_sq[belong[tmpi][tmpj]][k] = 1;
mp[tmpi][tmpj] = k;
DFS();
mp[tmpi][tmpj] = 0;
vis_Line[tmpi][k] = vis_Row[tmpj][k] = vis_sq[belong[tmpi][tmpj]][k] = 0;
}
}}
int main()
{
for(int i=9;i>=1;--i)
for(int j=9;j>=1;--j)
{
scanf("%d",&mp[i][j]);
vis_Line[i][mp[i][j]] = vis_Row[j][mp[i][j]] = vis_sq[belong[i][j]][mp[i][j]] = 1;
}
DFS();
printf("%d\n",ans == 0 ? -1 : ans);}
-
0
搜索+剪枝>_<
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int tot;
int r;
}row[11];
int map[11][11];
int book1[11][10],book2[11][10],book3[4][4][10];
int score[9][9]= {{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};
int ans=-1;
bool cmp(node a,node b){
return a.tot>b.tot;
}
void init()
{
int i,j,tot;
memset(book1,0,sizeof(book1));
memset(book2,0,sizeof(book2));
memset(book3,0,sizeof(book3));
for(i=1; i<=9; i++)
{
tot=0;
for(j=1; j<=9; j++)
{
cin>>map[i][j];
if(map[i][j]!=0)
{
tot++;
book1[i][map[i][j]]=1;
book2[j][map[i][j]]=1;
book3[(i-1)/3][(j-1)/3][map[i][j]]=1;
}
}
row[i].tot=tot;
row[i].r=i;
}
sort(row+1,row+10,cmp);
}
void dfs(int s,int t)
{
int k;
if(s>9)
{
int i,j,cou=0;
for(i=1; i<=9; i++)
{
for(j=1; j<=9; j++)
{
cou+=map[i][j]*score[i-1][j-1];
}
}
ans=max(ans,cou);
return;
}if(t>9) dfs(s+1,1);
else if(map[row[s].r][t]==0)
{
for(k=1; k<=9; k++)
{
int a=(row[s].r-1)/3;
int b=(t-1)/3;
if(!(book1[row[s].r][k]||book2[t][k]||book3[a][b][k]))
{
map[row[s].r][t]=k;
book1[row[s].r][k]=1;
book2[t][k]=1;
book3[a][b][k]=1;
dfs(s,t+1);
map[row[s].r][t]=0;
book1[row[s].r][k]=0;
book2[t][k]=0;
book3[a][b][k]=0;
}
}
}
else dfs(s,t+1);
}
int main()
{
init();
dfs(1,1);
printf("%d",ans);
return 0;
}
```-
wuwangmao @ 2016-08-23 00:12:04
先以每行已填的数的个数排序,优先搜索已填的数最多的那一行,来达到剪枝
-
-
0
不需要优化，数据弱
#include <cstdio>int G[9][9];
int h[9][10]={0}; //h[i][j]表示第i行(横向)有没有j
int l[9][10]={0}; //l[i][j]表示第i列(纵向)有没有j
int q[9][10]={0}; //q[i][j]表示第i个九宫格有没有j
//注意是[9][10]!!!!!!!!!!!!!!int getscore(){
int sum=0,k;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(i==0||i==8||j==0||j==8)
k=6;
else if(i==1||i==7||j==1||j==7)
k=7;
else if(i==2||i==6||j==2||j==6)
k=8;
else if(i==3||i==5||j==3||j==5)
k=9;
else if(i==4&&j==4)
k=10;
sum+=G[i][j]*k;
}
}
return sum;
}int getnum(int i,int j){//获取九宫格的编号
return 3*(i/3)+(j/3);
}int update(int p,int i,int j,int x){
if(p==1)
G[i][j]=x;
else
G[i][j]=0;
h[i][x]=p;
l[j][x]=p;
q[getnum(i,j)][x]=p;
}int isok(int i,int j,int x){
int flag=1;
flag*=h[i][x]==0;
flag*=l[j][x]==0;
flag*=q[getnum(i,j)][x]==0;
return flag;
}int ans=0;
void dfs(int u){
if(u==81){
int score=getscore();
ans=score>ans?score:ans;
return;
}
int pi=u/9,pj=u-9*(u/9);
if(G[pi][pj]!=0)
dfs(u+1);
else{
for(int x=1;x<=9;x++){
if(isok(pi,pj,x)){
update(1,pi,pj,x);
dfs(u+1);
update(0,pi,pj,x);
}
}
}
}int main(){
//freopen("in.txt","r",stdin);
for(int i=8;i>=0;i--)
for(int j=8;j>=0;j--){
int x;
scanf("%1d",&x);
if(x)
update(1,i,j,x);
}
dfs(0);
if(ans==0)
printf("-1");
else
printf("%d",ans);
return 0;
}-
Pia @ 2016-08-20 07:40:25
卡数据好评
-
-
0
每次都从可以填的数最少的格子开始搜 搜到一组解的时候和记录的最大值比较一下
#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;
bitset<15> r[12],c[12],gong[12];
int g[15][15],num=81,ans;
int v[9][9]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};int getnum(int i,int j){
bitset<15> tmp=r[i]|c[j]|gong[i/3*3+j/3];
return (9-tmp.count()==0)? 1000:9-tmp.count();
}void check(){
int sum=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
sum+=g[i][j]*v[i][j];
if(sum>ans) ans=sum;
}bool dfs(int a){
if(!a) {
check();return true;
}
int minx,miny,minnum=1000,flag=false;
for(int x=0;x<9;x++)
for(int y=0;y<9;y++)
if(!g[x][y] && getnum(x,y)<minnum) minnum=getnum(x,y),minx=x,miny=y;
if(minnum==1000) {return false;}
bitset<15> tmp=r[minx]|c[miny]|gong[minx/3*3+miny/3];
for(int t=1;t<=9;t++){
if(!tmp[t]){
r[minx][t]=1;c[miny][t]=1;gong[minx/3*3+miny/3][t]=1;g[minx][miny]=t;
if(dfs(a-1)) flag=true;
r[minx][t]=0;c[miny][t]=0;gong[minx/3*3+miny/3][t]=0;g[minx][miny]=0;
}
}
return flag;
}int main(){
for(int i=0;i<=10;i++) r[i].reset(),c[i].reset(),gong[i].reset();
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
scanf("%d",&g[i][j]);
if(g[i][j]) r[i][g[i][j]]=1,c[j][g[i][j]]=1,gong[i/3*3+j/3][g[i][j]]=1,num--;
}
if(!dfs(num)) printf("-1");
else printf("%d",ans);
return 0;
} -
0
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
int x , y , data;
};
int f[ 10 ][ 10 ] , map[ 10 ][ 10 ] , n = 9 , tot , ans;
bool hang[ 10 ][ 10 ] , lie[ 10 ][ 10 ] , qua[ 4 ][ 4 ][ 10 ];
void Init(){
int tem , sc[ 10 ];
for( int i = 1 ; i <= 5 ; i++ )
sc[ i ] = i + 5;
for( int i = 1 ; i <= n ; i++ ){
if ( i <= 5 ) tem = i;
else tem = n - i + 1;
for( int j = 1 ; j <= tem ; j++ )
f[ i ][ j ] = sc[ j ] , f[ i ][ n - j + 1 ] = sc[ j ];
for( int j = tem + 1 ; j <= n - tem ; j++ )
f[ i ][ j ] = tem + 5;
}
}
void Change( int x , int y , int data , bool p ){
hang[ x ][ data ] = p;
lie[ y ][ data ] = p;
qua[ ( x + 2 ) / 3 ][ ( y + 2 ) / 3 ][ data ] = p;
}
bool Get( int x , int y , int k ){
if ( hang[ x ][ k ] ) return true;
if ( lie[ y ][ k ] ) return true;
if ( qua[ ( x + 2 ) / 3 ][ ( y + 2 ) / 3 ][ k ] ) return true;
return false;
}
Node Get_can(){
Node p;
int minn = ( int )( 1e9 );
for( int i = 1 ; i <= n ; i++ )
for( int j = 1 ; j <= n ; j++ )
if ( map[ i ][ j ] == 0 ){
int num = 0;
for( int k = 1 ; k <= n ; k++ )
if ( !Get( i , j , k ) ) num++;
if ( minn > num ){
minn = num;
p.x = i;
p.y = j;
}
}
p.data = minn;
return p;
}
int Get_sum(){
int rem = 0;
for( int i = 1 ; i <= n ; i++ )
for( int j = 1 ; j <= n ; j++ )
rem += f[ i ][ j ] * map[ i ][ j ];
return rem;
}
void Dfs( int x ){
if ( x > tot ){
ans = max( ans , Get_sum() );
return;
}
Node p = Get_can();
if ( p.data == 0 ) return;
for( int i = 1 ; i <= n ; i++ )
if ( !Get( p.x , p.y , i ) ){
map[ p.x ][ p.y ] = i;
Change( p.x , p.y , i , true );
Dfs( x + 1 );
Change( p.x , p.y , i , false );
map[ p.x ][ p.y ] = 0;
}
}
int main(){
tot = 0;
Init();
for( int i = 1 ; i <= n ; i++ )
for( int j = 1 ; j <= n ; j++ ){
scanf( "%d" , &map[ i ][ j ] );
if ( map[ i ][ j ] )
Change( i , j , map[ i ][ j ] , true );
else tot++;
}
ans = -1;
Dfs( 1 );
ans == -1 ? printf( "-1\n" ) : printf( "%d\n" , ans );
return 0;
} -
0
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;int can[10][10];
int a[10][10];
bool bx[10][10];
bool by[10][10];
bool bb[4][4][10];
int mmax=0;
int n=0;
int scr[10][10]=
{
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6},
};
int ans=-1;bool f(int x,int y,int k)
{
if(!bx[x][k]&&!by[y][k]&&!bb[(x+2)/3][(y+2)/3][k])
return true;
return false;
}
void dfs(int X)
{
if(X>n)
{
int mmax=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(a[i][j]==0)
return ;
else
mmax+=a[i][j]*scr[i][j];
ans=max(mmax,ans);
return ;
}int x,y,mmin=99999999;
memset(can,0,sizeof(can));
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(!a[i][j])
{
for(int k=1;k<=9;k++)
if ( f(i,j,k) ) can[i][j]++;if(can[i][j]<mmin)
{
mmin=can[i][j];
x=i; y=j;
}
if(mmin==1) break;
}if(mmin==0) return ;
if(mmin==99999999)
{
int mmax=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(a[i][j]==0)
return ;
else
mmax+=a[i][j]*scr[i][j];
ans=max(mmax,ans);
return ;
}for(int i=1;i<=9;i++)
if( f(x,y,i) )
{
a[x][y]=i;bx[x][i]=true;
by[y][i]=true;
bb[(x+2)/3][(y+2)/3][i]=true;dfs(X+1);
bx[x][i]=false;
by[y][i]=false;
bb[(x+2)/3][(y+2)/3][i]=false;a[x][y]=0;
}}
int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0) n++;
else
{
bx[i][a[i][j]]=true;
by[j][a[i][j]]=true;
bb[(i+2)/3][(j+2)/3][a[i][j]]=true;
}
}dfs(1);
cout<<ans;
return 0;
}主要就是搜索时选择可能性最小的搜索 有选择性的搜索 具体见
www.ofsxb.com -
0
再发一个DLX的
#include<cstdio>
#include<algorithm>#define Rep(i) for (int i=0;i<9;i++)
#define in(i,j,x,y) (i>=x&&i<=y&&j>=x&&j<=y)
using namespace std;const int R=9*9*9+19,C=9*9*4+19;
struct node;typedef node* nd;
struct node
{
nd L,R,U,D,col;
int sz,row;
} ND[R*C];
nd rt,Col[C],Row[R];
int A[9][9],cnt,tmp,Ans,a,b,c;int IDx(int i,int j,int k) {return i*81+j*9+k;}
int IDy(int k,int i,int j) {return k*81+i*9+j+1;}
void reID(int x,int &a,int &b,int &c) {x--;c=x%9;x/=9;b=x%9;x/=9;a=x;}
int score(int x,int y)
{
return in(x,y,4,4)?10:in(x,y,3,5)?9:in(x,y,2,6)?8:in(x,y,1,7)?7:6;
}void Add_node(int r,int c)
{
nd x=&ND[++cnt];x->col=Col[c];x->row=r;
if (Row[r]==0) {Row[r]=x;x->L=x->R=x;}
Row[r]->L->R=x,x->L=Row[r]->L,x->R=Row[r],Row[r]->L=x;
Col[c]->U->D=x,x->U=Col[c]->U,x->D=Col[c],Col[c]->U=x,Col[c]->sz++;
}
void remove(nd x)
{
x->L->R=x->R;x->R->L=x->L;
for (nd i=x->D;i!=x;i=i->D)
for (nd j=i->R;j!=i;j=j->R) j->U->D=j->D,j->D->U=j->U,j->col->sz--;
}
void remuse(nd x)
{
for (nd i=x->U;i!=x;i=i->U)
for (nd j=i->R;j!=i;j=j->R) j->U->D=j->D->U=j,j->col->sz++;
x->L->R=x->R->L=x;
}
int Dancing()
{
if (rt->R==rt) return Ans=max(Ans,tmp),1;
int Min=1<<30,f=0;nd x;
for (nd i=rt->R;i!=rt;i=i->R) if (i->sz<Min) Min=i->sz,x=i;
remove(x);
for (nd i=x->D;i!=x;i=i->D)
{
reID(i->row,a,b,c),tmp+=score(a,b)*(c+1);
for (nd j=i->R;j!=i;j=j->R) remove(j->col);
f|=Dancing();
for (nd j=i->L;j!=i;j=j->L) remuse(j->col);
reID(i->row,a,b,c),tmp-=score(a,b)*(c+1);
}
remuse(x);
return f;
}int main()
{
Rep(i) Rep(j) scanf("%d",&A[i][j]);
rt=Col[0]=&ND[0];
for (int i=1;i<=9*9*4;i++) Col[i]=&ND[i];
for (int i=1;i<=9*9*4;i++)
Col[i]->L=Col[i-1],Col[i]->R=Col[i+1],
Col[i]->U=Col[i]->D=Col[i],Col[i]->sz=0;
rt->L=Col[9*9*4],rt->R=Col[1];Col[cnt=9*9*4]->R=rt;
Rep(i) Rep(j) for (int k=1;k<=9;k++)
if (A[i][j]==k||!A[i][j])
{
int r=IDx(i,j,k);Row[r]=0;
Add_node(r,IDy(0,i,j));
Add_node(r,IDy(1,i,k-1));
Add_node(r,IDy(2,j,k-1));
Add_node(r,IDy(3,i/3*3+j/3,k-1));
}
printf("%d\n",Dancing()?Ans:-1);
}-
浩如烟海 @ 2015-01-29 20:33:41
前排ORZ
-
hwwyx @ 2015-01-30 10:19:52
orz 跪
-
huanghongxun @ 2015-10-21 10:42:20
orz DLX
-
Firstlast @ 2016-04-24 12:03:08
Orz DLX
-
-
0
#include<cstdio>
#include<cstring>
#include<algorithm>#define Rep(i) for (int i=1;i<=9;i++)
#define ID(i,j) ((i-1)/3*3+(j-1)/3+1)
#define in(i,x,y) (i>=x&&i<=y)
using namespace std;typedef int Matrix[10][10];
Matrix P,A,can;
int Fx[10][10],Fy[10][10],Fz[10][10],xx[10];
struct node {int x,y;} List[81+19];
int Ans=-1,tmp,x,cnt;int cmp(node A,node B)
{
if (xx[A.x]!=xx[B.x]) return xx[A.x]<xx[B.x];
return can[A.x][A.y]<can[B.x][B.y];
}
void DFS(int cur)
{
if (cur==cnt) {Ans=max(Ans,tmp);return;}
int x=List[cur].x,y=List[cur].y;
Rep(k) if (Fx[x][k]&&Fy[y][k]&&Fz[ID(x,y)][k])
{
tmp+=k*P[x][y];
Fx[x][k]=Fy[y][k]=Fz[ID(x,y)][k]=0;
DFS(cur+1);
Fx[x][k]=Fy[y][k]=Fz[ID(x,y)][k]=1;
tmp-=k*P[x][y];
}
}int main()
{
Rep(i) Rep(j) Fx[i][j]=Fy[i][j]=Fz[i][j]=1;
Rep(i) Rep(j)
P[i][j]=
(in(i,5,5)&&in(j,5,5)?10:
(in(i,4,6)&&in(j,4,6)?9:
(in(i,3,7)&&in(j,3,7)?8:
(in(i,2,8)&&in(j,2,8)?7:6))));
Rep(i) Rep(j)
{
scanf("%d",&x);
if (x) tmp+=x*P[i][j],Fx[i][x]=Fy[j][x]=Fz[ID(i,j)][x]=0;
A[i][j]=x;
}
Rep(i) Rep(j)
if (!A[i][j])
{
List[cnt++]=(node){i,j};xx[i]++;
Rep(k) can[i][j]+=Fx[i][k]&&Fy[j][k]&&Fz[ID(i,j)][k];
}
sort(List,List+cnt,cmp);
DFS(0);
printf("%d\n",Ans);
} -
0
#include<cmath>
#include<iostream>
using namespace std;
int a[10][10],h[10],hs[10],ss[10],nine[10],sort[10],q[10],ans=-1,st=511;
void swap(int*a,int*b)
{
*a^=*b;
*b^=*a;
*a^=*b;
}
int ten(int x)
{
return(int)log2(x)+1;
}
void dfs(int k)
{
int c,i,j,l,get,num,pos,p;
if(k==10)
{
c=a[5][5]*10;
for(l=2;l<=5;l++)
{
for(i=l;i<=10-l;i++)
c+=(4+l)*(a[i][l-1]+a[i][11-l]);
for(j=l;j<=10-l;j++)
c+=(4+l)*(a[l-1][j]+a[11-l][j]);
c+=(4+l)*(a[l-1][l-1]+a[l-1][11-l]+a[11-l][l-1]+a[11-l][11-l]);
}
ans=max(ans,c);
}
else
{
i=sort[k];
pos=st&~h[i];
p=pos&-pos;
h[i]|=p;
j=ten(p);
get=st&~(hs[i]|ss[j]|nine[(i-1)/3*3+(j-1)/3+1]);
while(get)
{
num=get&-get;
get^=num;
a[i][j]=ten(num);
hs[i]|=num;
ss[j]|=num;
nine[(i-1)/3*3+(j-1)/3+1]|=num;
if(pos==p)
dfs(k+1);
else
dfs(k);
hs[i]^=num;
ss[j]^=num;
nine[(i-1)/3*3+(j-1)/3+1]^=num;
}
h[i]^=p;
}
}
main()
{
int i,j,k=1;
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
{
sort[i]=i;
cin>>a[i][j];
if(a[i][j])
{
h[i]|=1<<(j-1);
if(((hs[i]|ss[j]|nine[(i-1)/3*3+(j-1)/3+1])&(1<<(a[i][j]-1)))==1)
{
cout<<-1;
return 0;
}
hs[i]|=1<<(a[i][j]-1);
ss[j]|=1<<(a[i][j]-1);
nine[(i-1)/3*3+(j-1)/3+1]|=1<<(a[i][j]-1);
}
else
q[i]++;
}
for(i=1;i<9;i++)
for(j=i+1;j<=9;j++)
if(q[sort[i]]>q[sort[j]])
swap(&sort[i],&sort[j]);
while(!q[sort[k]])
k++;
dfs(k);
cout<<ans;
} -
0
上海红茶馆 via libjudge
编译成功测试数据 #0: Accepted, time = 14 ms, mem = 3372 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #6: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #7: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 3372 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 3372 KiB, score = 5
测试数据 #10: Accepted, time = 138 ms, mem = 3372 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 3372 KiB, score = 5
测试数据 #12: Accepted, time = 153 ms, mem = 3372 KiB, score = 5
测试数据 #13: Accepted, time = 184 ms, mem = 3372 KiB, score = 5
测试数据 #14: Accepted, time = 183 ms, mem = 3372 KiB, score = 5
测试数据 #15: Accepted, time = 197 ms, mem = 3372 KiB, score = 5
测试数据 #16: Accepted, time = 285 ms, mem = 3372 KiB, score = 5
测试数据 #17: Accepted, time = 211 ms, mem = 3372 KiB, score = 5
测试数据 #18: Accepted, time = 211 ms, mem = 3372 KiB, score = 5
测试数据 #19: Accepted, time = 241 ms, mem = 3372 KiB, score = 5
Summary: Accepted, time = 1937 ms, mem = 3372 KiB, score = 100dancing link 每次搜索可选择数最少的列
-
0
编译通过...
├ 测试数据 01：答案正确... (0ms, 676KB)
├ 测试数据 02：答案正确... (136ms, 676KB)
├ 测试数据 03：答案正确... (167ms, 676KB)
├ 测试数据 04：答案正确... (137ms, 676KB)
├ 测试数据 05：答案正确... (138ms, 676KB)
├ 测试数据 06：答案正确... (123ms, 676KB)
├ 测试数据 07：答案正确... (137ms, 676KB)
├ 测试数据 08：答案正确... (123ms, 676KB)
├ 测试数据 09：运行超时... (?, 676KB)
├ 测试数据 10：运行超时... (?, 632KB)
├ 测试数据 11：答案正确... (1618ms, 632KB)
├ 测试数据 12：运行超时... (?, 632KB)
├ 测试数据 13：答案正确... (1645ms, 632KB)
├ 测试数据 14：答案正确... (1901ms, 632KB)
├ 测试数据 15：运行超时... (?, 632KB)
├ 测试数据 16：运行超时... (?, 632KB)
├ 测试数据 17：答案正确... (1573ms, 632KB)
├ 测试数据 18：运行超时... (?, 632KB)
├ 测试数据 19：答案正确... (1707ms, 632KB)
├ 测试数据 20：答案正确... (1940ms, 632KB)---|---|---|---|---|---|---|---|-
Unaccepted / 70 / ? / 676KB -
0
编译通过...
├ 测试数据 01：答案正确... (0ms, 580KB)
├ 测试数据 02：答案错误... (0ms, 580KB)
├ 测试数据 03：答案正确... (0ms, 580KB)
├ 测试数据 04：答案正确... (0ms, 580KB)
├ 测试数据 05：答案正确... (0ms, 580KB)
├ 测试数据 06：答案正确... (0ms, 580KB)
├ 测试数据 07：答案正确... (0ms, 580KB)
├ 测试数据 08：答案正确... (0ms, 580KB)
├ 测试数据 09：答案错误... (43ms, 580KB)
├ 测试数据 10：答案正确... (0ms, 580KB)
├ 测试数据 11：答案正确... (129ms, 584KB)
├ 测试数据 12：答案正确... (0ms, 580KB)
├ 测试数据 13：答案正确... (340ms, 584KB)
├ 测试数据 14：答案正确... (918ms, 584KB)
├ 测试数据 15：答案错误... (325ms, 584KB)
├ 测试数据 16：答案正确... (356ms, 584KB)
├ 测试数据 17：运行超时... (?, 584KB)
├ 测试数据 18：答案正确... (918ms, 584KB)
├ 测试数据 19：答案正确... (1215ms, 584KB)
├ 测试数据 20：答案正确... (1496ms, 584KB)
VijosNT Mini 2.0.5.7 Special for Vijos编译通过...
├ 测试数据 01：答案正确... (24ms, 580KB)
├ 测试数据 02：答案正确... (32ms, 580KB)
├ 测试数据 03：答案正确... (1805ms, 580KB)
├ 测试数据 04：答案正确... (35ms, 580KB)
├ 测试数据 05：答案正确... (0ms, 580KB)
├ 测试数据 06：答案正确... (51ms, 580KB)
├ 测试数据 07：答案正确... (47ms, 580KB)
├ 测试数据 08：答案正确... (16ms, 580KB)
├ 测试数据 09：答案正确... (149ms, 580KB)
├ 测试数据 10：答案正确... (121ms, 580KB)
├ 测试数据 11：答案正确... (364ms, 584KB)
├ 测试数据 12：答案正确... (39ms, 580KB)
├ 测试数据 13：答案正确... (1512ms, 584KB)
├ 测试数据 14：答案正确... (1028ms, 584KB)
├ 测试数据 15：答案正确... (528ms, 584KB)
├ 测试数据 16：答案正确... (555ms, 584KB)
├ 测试数据 17：运行超时... (?, 584KB)
├ 测试数据 18：答案正确... (1106ms, 584KB)
├ 测试数据 19：答案正确... (1387ms, 584KB)
├ 测试数据 20：答案正确... (1731ms, 584KB)---|---|---|---|---|---|---|---|-
Unaccepted / 95 / ? / 584KB
lyyyzx
LV 10
@ 2016-11-12 16:59:57
- 1
