苦难的题目，我做着题只有一个想法：深搜，，暴力搜索！但是就连样例都超时了，我就直接找题解去了。
网上找到一个题解，用位运算做的，大概看了下就开始仿造着写，去掉了感觉无用的功能（其实很有用），结果超时了。。。超时代码如下，75分。
#include <stdio.h>
#define getindex(t) ({\
int i;\
switch(t){\
case 1:\
i = 0;\
break;\
case 2:\
i = 1;\
break;\
case 4:\
i = 2;\
break;\
case 8:\
i = 3;\
break;\
case 16:\
i = 4;\
break;\
case 32:\
i = 5;\
break;\
case 64:\
i = 6;\
break;\
case 128:\
i = 7;\
break;\
case 256:\
i = 8;\
break;\
}\
i;\
})
#define getboxid(i, j) ((3 * ((i) / 3)) + ((j) / 3))
int rol[9], //记录横排出现的数字
col[9], //记录竖排出现的数字
box[9], //记录九各宫出现的数字
use[9]; //记录横排
int ans = –1;
//初始化为-1而不是0
int map[9][9];
int mul[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}};
void cal(void)
{
int i, j;
int tmp = 0;
for(i = 0; i < 9; i++){
for(j = 0; j < 9; j++){
tmp += map[i][j] * mul[i][j];
}
}
if(tmp > ans){
ans = tmp;
}
}
void srch(int i)
{
int j, x, y;
int pos, p;
if(i == 9){
cal();
return ;
}
x = 511 ^ use[i];
if(x == 0){
srch(i + 1);
return;
//掉了return
}
y = x & -x;
use[i] |= y;
j = getindex(y);
pos = 511 ^ (rol[i]|col[j]|box[getboxid(i, j)]);
while(pos > 0){
p = pos & -pos;
pos ^= p;
map[i][j] = getindex(p) + 1;
rol[i] |= p;
col[j] |= p;
box[getboxid(i, j)] |= p;
srch(i);
rol[i] ^= p;
col[j] ^= p;
box[getboxid(i, j)] ^= p;
}
use[i] ^= y;
}
int main(void)
{
int i, j;
int p;
freopen(“abc.txt”, “r”, stdin);
for(i = 0; i < 9; i++){
for(j = 0; j < 9; j++){
scanf(“%d“, &map[i][j]);
if(map[i][j] > 0){
use[i] |= 1 << j;
p = 1 << (map[i][j] – 1);
if(((rol[i] & p)) || ((col[j] & p))
|| ((box[getboxid(i, j)] & p))){
printf(“-1\n“);
return 0;
}
rol[i] |= p;
col[j] |= p;
box[getboxid(i, j)] |= p;
}
}
}
srch(0);
printf(“%d\n“, ans);
return 0;
}
后来找了好久才想起来是把这个重要的剪枝去掉了（就是我认为不重要的部分。）
修改代码如下：
#include <stdio.h>
#define getindex(t) ({\
int i;\
switch(t){\
case 1:\
i = 0;\
break;\
case 2:\
i = 1;\
break;\
case 4:\
i = 2;\
break;\
case 8:\
i = 3;\
break;\
case 16:\
i = 4;\
break;\
case 32:\
i = 5;\
break;\
case 64:\
i = 6;\
break;\
case 128:\
i = 7;\
break;\
case 256:\
i = 8;\
break;\
}\
i;\
})
#define getboxid(i, j) ((3 * ((i) / 3)) + ((j) / 3))
int rol[9], //记录横排出现的数字
col[9], //记录竖排出现的数字
box[9], //记录九各宫出现的数字
use[9]; //记录横排
int count[9]; //每行值为0的个数
int hk[9]; //按照这里的顺序进行深搜!! 重要剪枝
int ans = –1;
//初始化为-1而不是0
int map[9][9];
int mul[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}};
void cal(void)
{
int i, j;
int tmp = 0;
for(i = 0; i < 9; i++){
for(j = 0; j < 9; j++){
tmp += map[i][j] * mul[i][j];
}
}
if(tmp > ans){
ans = tmp;
}
}
void srch(int t)
{
int i, j, x, y;
int pos, p;
if(t == 9){
//这里是t不是i
cal();
return ;
}
i = hk[t];
x = 511 ^ use[i];
if(x == 0){
srch(t + 1);
return;
//掉了return
}
y = x & -x;
use[i] |= y;
j = getindex(y);
pos = 511 ^ (rol[i]|col[j]|box[getboxid(i, j)]);
while(pos > 0){
p = pos & -pos;
pos ^= p;
map[i][j] = getindex(p) + 1;
rol[i] |= p;
col[j] |= p;
box[getboxid(i, j)] |= p;
srch(t);
rol[i] ^= p;
col[j] ^= p;
box[getboxid(i, j)] ^= p;
}
use[i] ^= y;
}
int main(void)
{
int i, j;
int p;
for(i = 0; i < 9; i++){
for(j = 0; j < 9; j++){
scanf(“%d“, &map[i][j]);
if(map[i][j] > 0){
use[i] |= 1 << j;
p = 1 << (map[i][j] – 1);
if(((rol[i] & p)) || ((col[j] & p))
|| ((box[getboxid(i, j)] & p))){
printf(“-1\n“);
return 0;
}
rol[i] |= p;
col[j] |= p;
box[getboxid(i, j)] |= p;
}else{
count[i]++;
}
}
}
for(i = 0; i < 9; i++){
hk[i] = i;
}
for(i = 1; i < 9; i++){
p = hk[i];
for(j = i – 1; j >= 0 && count[hk[j]] > count[p]; j–){
hk[j + 1] = hk[j];
}
hk[j + 1] = p;
}
srch(0);
printf(“%d\n“, ans);
return 0;
}