Luogu P1074靶形数独【搜索/剪枝】By cellur925
2024-08-24 12:08:12
显然是一个搜索。但是开始没有任何的剪枝，暴力从\((1,1)\)点开始搜索，很自然地T了6个点。
#include<cstdio>
#include<algorithm>
using namespace std;
const int group[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 sco[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,num[50][50];
bool gong[50][50],hang[50][50],lie[50][50];
void review()
{
int val=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
val+=sco[i][j]*num[i][j];
// printf("%d\n",val);
ans=max(ans,val);
}
bool check(int x,int y,int w)
{
if(gong[group[x][y]][w]||hang[x][w]||lie[y][w]) return 0;
return 1;
}
void dfs(int x,int y)
{
if(x==10)
{
review();
return ;
}
int nx=x,ny=y+1;
if(ny==10) nx++,ny=1;
if(num[x][y]) dfs(nx,ny);
else
{
for(int i=1;i<=9;i++)
{
if(!check(x,y,i)) continue;
gong[group[x][y]][i]=1;
hang[x][i]=1;
lie[y][i]=1;
num[x][y]=i;
dfs(nx,ny);
gong[group[x][y]][i]=0;
hang[x][i]=0;
lie[y][i]=0;
num[x][y]=0;
}
}
}
int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
int x=0;
scanf("%d",&x);
if(!x) continue;
num[i][j]=x;
hang[i][x]=1;
lie[j][x]=1;
gong[group[i][j]][x]=1;
}
dfs(1,1);
printf("%d",ans==0 ? -1 : ans);
return 0;
}
考虑剪枝。从人类智慧的角度出发，如果是我们玩数独虽然我好像没怎么玩过，我们一定是从填的多的区域出发，因为有更少的决策可供我们选择。那么在这里我们也可以借鉴这个思路，每次统计一下每行每列的有多少数是已经填了的，得到一个最优的坐标，从它出发进行搜索。这个算法保证了我们每次搜的一定是没有填数的，使复杂度优秀了许多。
#include<cstdio>
#include<algorithm>
using namespace std;
const int group[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 sco[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 cn,ans,num[50][50];
int cnt_hang[50],cnt_lie[50];
bool gong[50][50],hang[50][50],lie[50][50];
void review()
{
int val=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
val+=sco[i][j]*num[i][j];
// printf("%d\n",val);
ans=max(ans,val);
}
bool check(int x,int y,int w)
{
if(gong[group[x][y]][w]||hang[x][w]||lie[y][w]) return 0;
return 1;
}
void dfs(int x,int y,int cnt)
{
if(cnt==81)
{
review();
return ;
}
for(int i=1;i<=9;i++)
{
if(!check(x,y,i)) continue;
gong[group[x][y]][i]=1;
hang[x][i]=1;
lie[y][i]=1;
num[x][y]=i;
cnt_hang[x]++;cnt_lie[y]++;
int qwq=-1,qaq=-1,bx=0,by=0;
for(int j=1;j<=9;j++)
if(cnt_hang[j]>qwq&&cnt_hang[j]<9)
qwq=cnt_hang[j],bx=j;
for(int j=1;j<=9;j++)
if(cnt_lie[j]>qaq&&(!num[bx][j]))
qaq=cnt_lie[j],by=j;
dfs(bx,by,cnt+1);
gong[group[x][y]][i]=0;
hang[x][i]=0;
lie[y][i]=0;
num[x][y]=0;
cnt_hang[x]--;cnt_lie[y]--;
}
}
int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
int x=0;
scanf("%d",&x);
if(!x) continue;
num[i][j]=x;
cnt_hang[i]++;
cnt_lie[j]++;
hang[i][x]=1;
lie[j][x]=1;
gong[group[i][j]][x]=1;
cn++;
}
int qwq=-1,qaq=-1,bx=0,by=0;
for(int i=1;i<=9;i++)
if(cnt_hang[i]>qwq&&cnt_hang[i]<9)
qwq=cnt_hang[i],bx=i;
for(int i=1;i<=9;i++)
if(cnt_lie[i]>qaq&&(!num[bx][i]))//注意这里找一个没有填数的坐标
qaq=cnt_lie[i],by=i;
dfs(bx,by,cn);
printf("%d",ans==0 ? -1 : ans);
return 0;
}
Warning
开始写自己的暴力写法的时候傻了两次：
①没输入输出（？？？）果然T的无可救药
②因为我确定宫和价值都是用数组打出表存的，而开始把数组开的很大，\(50*50\)，但是我们打出的表的部分不是另起一行，编译后会被理解连续的一段，于是我们要限制数组大小，使恰好能够填入数。
最新文章
- spring MVC配置详解
- C++之多态的一个例子
- 转：python webdriver API 之下载文件
- linux云计算集群架构学习笔记:rhel7基本命令操作
- d3可视化实战03：神奇的superformula
- MySql按指定天数进行分组数据统计分析 1
- poj 1068 Parencodings 模拟
- 用sftp上传文件至linux服务器
- JSP中的九大隐式对象及四个作用域
- Maven优雅的添加第三方Jar包
- linux ubuntu系统下MySQL的安装及设置
- python杂记二
- Vue自学
- js获取当前日期时间“yyyy-MM-dd HH:MM:SS”
- 让vim不要自动添加新的注释行
- day_6.23py线程
- python之模块calendar(汇集了日历相关的操作)
- 如何实现UI层的松耦合
- Power BI连接至Amazon Redshift
- 【找规律】【递推】【二项式定理】Codeforces Round #419 (Div. 1) B. Karen and Test