首页 > 代码库 > 洛谷OJ 1074 靶型sudoku dfs(搜索顺序优化)
洛谷OJ 1074 靶型sudoku dfs(搜索顺序优化)
https://www.luogu.org/problem/show?pid=1074
题意:靶型sudoku 问填完的最大得分?
//优化:从可能性小的开始搜索,把地图分数设置成常量数组,接着暴力即可
#include <bits/stdc++.h> using namespace std; const int N=2e2+20; int row[N][N],col[N][N],vis[N][N];//row[i][1~9] 第i列是否能选j int a[N][N]; int ans,n=9,cnt; int dist(int x,int y) { return (x/3)*3+(y/3); } bool check(int x,int y,int k) { if(row[x][k]||col[y][k]) return false; if(vis[dist(x,y)][k]) return false; return true; } int b[][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}, }; struct node{ int x,y; }; node getnext() //找到可能性小的 { node tmp; int min,t; tmp.x=n; tmp.y=n; min=n; for (int i=0;i<9;i++) for (int j=0;j<9;j++) if(!a[i][j]) { t=0; for (int k=1;k<=9;k++) if (!row[i][k]) if (!col[j][k]) if (!vis[dist(i,j)][k]) t++; if (t<min) { min=t; tmp.x=i; tmp.y=j; } } return tmp; } void dfs(int p) { if(p>=cnt)//需要填cnt个 { int res=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) res+=b[i][j]*a[i][j]; ans=max(ans,res); return; } node tmp=getnext(); if(tmp.x==n&&tmp.y==n) return; int x=tmp.x,y=tmp.y; for(int k=1;k<=9;k++) { if(check(x,y,k)) { row[x][k]=col[y][k]=vis[dist(x,y)][k]=1; a[x][y]=k; dfs(p+1); row[x][k]=col[y][k]=vis[dist(x,y)][k]=0; a[x][y]=0; } } } int main() { int n=9; ans=-1; cnt=n*n; memset(vis,0,sizeof(vis)); memset(col,0,sizeof(col)); memset(row,0,sizeof(row)); for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { scanf("%d",&a[i][j]); if(a[i][j]) { row[i][a[i][j]]=1; col[j][a[i][j]]=1; vis[dist(i,j)][a[i][j]]=1; cnt--;// } } } dfs(0); cout<<ans<<endl; return 0; }
洛谷OJ 1074 靶型sudoku dfs(搜索顺序优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。