|
Description:
写一个做数独的程序，但是这个数独有一点不同的是，每个格子有一个权值，权值与在格子上的数字乘积之和为总分，求最大能有多少分。
格子的权值规律如下
从白色的框到中央，依次为6,7,8,9,10
Input:
数独局面
Output:
answer
Analysis:
框架上就是dfs搜索，但是要有一个贪心的策略是，从有最少空格的行开始，因为，越少的空格在某一行就越能确定答案，可以减少dfs树的深度。里面还有一些细节，比如Get_point函数的写法上就有递推的意思。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<cmath>
#include<iterator>
#include<bitset>
#include<stdio.h>
#include<unordered_set>
#include<unordered_map>
#include<ctime>
#include<assert.h>
#include<cstring>
#include<array>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long LL;
const int INF = 1 << 30;
const int maxn = 11;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1);
int pic[maxn][maxn],n,tot_id;
int vis[3][10][10],ans;
vector<pair<int, int> > rows;
vector < pair<int, int> >id2cor;
inline int Get_grid(int r, int c) {
return ((r - 1) / 3 * 3 + (c - 1) / 3);
}
inline int Get_point(int r, int c) {
if (r == 1 || r == 9 || c == 1 || c == 9) return 6;
if (r == 2 || r == 8 || c == 2 || c == 8) return 7;
if (r == 3 || r == 7 || c == 3 || c == 7) return 8;
if (r == 4 || r == 6 || c == 4 || c == 6) return 9;
if (r == 5 || c == 5) return 10;
}
inline bool OK(int r, int c, int g,int num) {
return !vis[0][r][num] && !vis[1][c][num] && !vis[2][g][num];
}
void Precal() {
rows.clear();
n = 9;
_rep(i, 1, n) {
int cnt = 0;
_rep(j, 1, n)if (pic[i][j] == 0) cnt++;
rows.push_back({ cnt,i });
}
sort(rows.begin(), rows.end());
ans = -1;
memset(vis, 0, sizeof(vis));
_rep(i,1,n)
_rep(j, 1, n) if(pic[i][j]){
int num = pic[i][j];
int g = Get_grid(i, j);
vis[0][i][num] = vis[1][j][num] = vis[2][Get_grid(i, j)][num] = 1;
}
tot_id = 0;
id2cor.resize(81);
for(auto it:rows) {
int row = it.second;
_rep(j, 1, n)if (!pic[row][j]) {
id2cor[tot_id++] = { row,j };
}
}
}
int Cal() {
int res = 0;
_rep(i,1,n)
_rep(j, 1, n) {
res += Get_point(i, j)*pic[i][j];
}
return res;
}
void DFS(int depth) {
if (depth == tot_id) {
int tmp = Cal();
ans = max(tmp, ans);
return;
}
int row = id2cor[depth].first, col = id2cor[depth].second;
int g = Get_grid(row, col);
_rep(num, 1, n) {
if (OK(row, col, g,num)){
vis[0][row][num] = vis[1][col][num] = vis[2][g][num] = 1;
pic[row][col] = num;
DFS(depth + 1);
pic[row][col] = 0;
vis[0][row][num] = vis[1][col][num] = vis[2][g][num] = 0;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);//用这个
cin.tie(0); //就能防止cin超时orz
_rep(i, 1, 9)
_rep(j,1,9){
cin >> pic[i][j];
}
Precal();
DFS(0);
cout << ans << endl;
return 0;
}
| 
转播
