P1074 暴搜代码
本文最后修改于 1005 天前,部分内容可能已经过时!
没错,就是这么暴力
#include <bits/stdc++.h>
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;
int sudoku[9][9];
bool check(int number,int hang,int lie)
{int i,j;
for(i=0;i<9;i++) //行
if(i!=lie&&sudoku[hang][i]==number) return false;
for(i=0;i<9;i++) //列
if(i!=hang&&sudoku[i][lie]==number) return false;
for(i=(hang/3)*3;i<=(hang/3)*3+2;i++) //九宫格
for(j=(lie/3)*3;j<=(lie/3)*3+2;j++)
if(i!=hang&&j!=lie&&sudoku[i][j]==number) return false;
return true;
}
void dfs(int step,int sum){
int x,y;
if(step<0) {
if(sum>ans) ans=sum;
return;
}
x=(step/9);y=(step%9);
if(sudoku[x][y]>0)
dfs(step-1,sum+sudoku[x][y]*score[x][y]);
else
for(int i=1;i<=9;i++)
if(check(i,x,y)) {
sudoku[x][y]=i;
dfs(step-1,sum+sudoku[x][y]*score[x][y]);
sudoku[x][y]=0;
}
}
int main(){
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
scanf("%d",&sudoku[i][j]);
ans=-1;
dfs(80,0);
printf("%d",ans);
}