洛谷 P1074 靶形数独/LOJ #2591. 「NOIP2009」靶形数独
思路
特别想说一下这道题，因为真的特!别!好!玩!
数独是啥？
数独都懂吧
(1.)每一行不能有一样的数字
(2.)每一列不能有一样的数字
(3.)每个(3*3)的九宫格不能有一样的数字
填出来你就赢了（好牛！！）
how to do
首先上来的感觉就是要搜索，那么，搜索的话，我们要想一下怎么搜，这里可以直接记录某一行某个数是否出现，某一列某个数是否出现，某个九宫格内某个数是否出现，前两个好弄，直接循环的时候记录就好了，最后一个怎么办？
而且怎么计算格子的分数呢？？一个一个乘？
所以，我们要解决的问题是：怎么计算格子的分数，怎么判断是第几个九宫格
- 一开始在想怎么计算这个格子的分数是多少，后来决定干脆直接开个(score)数组存下来得了，算的时候一乘就完事儿了
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 pd(int i, int j) {
if(i <= 3 && j <= 3) return 1;
if(i <= 3 && j <= 6) return 2;
if(i <= 3 && j <= 9) return 3;
if(i <= 6 && j <= 3) return 4;
if(i <= 6 && j <= 6) return 5;
if(i <= 6 && j <= 9) return 6;
if(i <= 9 && j <= 3) return 7;
if(i <= 9 && j <= 6) return 8;
if(i <= 9 && j <= 9) return 9;
}
然后我们就可以一行一行的搜索，填完一行再填下一行，然后就可以得到六十分的好成绩
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
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 pd(int i, int j) {
if(i <= 3 && j <= 3) return 1;
if(i <= 3 && j <= 6) return 2;
if(i <= 3 && j <= 9) return 3;
if(i <= 6 && j <= 3) return 4;
if(i <= 6 && j <= 6) return 5;
if(i <= 6 && j <= 9) return 6;
if(i <= 9 && j <= 3) return 7;
if(i <= 9 && j <= 6) return 8;
if(i <= 9 && j <= 9) return 9;
}
int a[11][11], hang[11][11], lie[11][11], sma[11][11];
int tot, ans = -10000;
void coun() {
int now = 0;
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
now += a[i][j] * score[i][j];
ans = max(ans, now);
return;
}
void dfs(int ho, int li) { //行、列、这一行填了多少个
if(ho == 10) { coun(); return; }
if(li == 10) dfs(ho + 1, 1);
if(!a[ho][li]) {
for(int i = 1; i <= 9; i++) {
if(!hang[ho][i] && !lie[li][i] && !sma[pd(ho, li)][i]) {
hang[ho][i] = lie[li][i] = sma[pd(ho, li)][i] = 1;
a[ho][li] = i; dfs(ho, li + 1); a[ho][li] = 0;
hang[ho][i] = lie[li][i] = sma[pd(ho, li)][i] = 0;
}
}
}
else dfs(ho, li + 1);
}
int main() {
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++) {
a[i][j] = read();
if(a[i][j]) {
sma[pd(i, j)][a[i][j]] = 1;
hang[i][a[i][j]] = 1;
lie[j][a[i][j]] = 1;
}
else tot++;
}
dfs(1, 1);
cout << ans << "
";
return 0;
}
怎么优化？
我不会优化呀！！怎么办！只能搜了……只见大佬说
从填数最多的一行开始填，这样要选择的数就少了，不合法的情况就可以省掉一些
然后就满分了(qwq)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
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 pd(int i, int j) {
if(i <= 3 && j <= 3) return 1;
if(i <= 3 && j <= 6) return 2;
if(i <= 3 && j <= 9) return 3;
if(i <= 6 && j <= 3) return 4;
if(i <= 6 && j <= 6) return 5;
if(i <= 6 && j <= 9) return 6;
if(i <= 9 && j <= 3) return 7;
if(i <= 9 && j <= 6) return 8;
if(i <= 9 && j <= 9) return 9;
}
int a[11][11], hang[11][11], lie[11][11], sma[11][11];
int tot, ans = -1;
struct node { int sum, line; } qwq[11];
bool cmp(node a, node b) {
return a.sum < b.sum;
}
void coun() {
int now = 0;
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
now += a[i][j] * score[i][j];
ans = max(ans, now);
return;
}
void dfs(int cnt, int ho, int li) { //行、列、这一行填了多少个
if(cnt == 10) { coun(); return; }
if(li == 10) dfs(cnt + 1, qwq[cnt + 1].line, 1);
if(!a[ho][li]) {
for(int i = 1; i <= 9; i++) {
if(!hang[ho][i] && !lie[li][i] && !sma[pd(ho, li)][i]) {
hang[ho][i] = lie[li][i] = sma[pd(ho, li)][i] = 1;
a[ho][li] = i; dfs(cnt, ho, li + 1); a[ho][li] = 0;
hang[ho][i] = lie[li][i] = sma[pd(ho, li)][i] = 0;
}
}
}
else dfs(cnt, ho, li + 1);
}
int main() {
for(int i = 1; i <= 9; i++) {
tot = 0;
for(int j = 1; j <= 9; j++) {
a[i][j] = read();
if(a[i][j]) {
sma[pd(i, j)][a[i][j]] = 1;
hang[i][a[i][j]] = 1;
lie[j][a[i][j]] = 1;
}
else tot++;
qwq[i].line = i, qwq[i].sum = tot;
}
}
sort(qwq + 1, qwq + 1 + 9, cmp);
dfs(1, qwq[1].line, 1);
cout << ans; return 0;
}
是的你赢了