NOIP 2009 靶形数独

本题要取得满分需要一定的剪枝，不过，一般的DFS+适当的数据结构可以获得80分。

代码如下（80分，4个测试点严重超时）：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #define MXN 10
004
005 typedef struct point
006 {
007     int i,j;
008 }point;
009
010 int dx[8] = {0,0,1,-1,1,-1,-1,1};
011 int dy[8] = {1,-1,1,-1,0,0,1,-1};
012
013 point empty[MXN * MXN];
014 int find;
015 int ecount;
016 long initmark;
017 int board[MXN][MXN];  //记录数字
018 int belong[MXN][MXN];  //某个位置所在的小区域编号
019 int rank[MXN][MXN];  //权重
020 int col[MXN] = {},row[MXN] = {};  //类似下面的
021 int part[MXN] = {};  //小区域中某个数字是否使用过
022 long max = 0;  //填入的数字可以增加的最大分值
023
024 void markbelong(int i,int j,int b)
025 {
026     int k;
027     belong[i][j] = b;
028     for(k = 0;k < 8;k ++)
029         belong[i + dx[k]][j + dy[k]] = b;
030 }
031
032 void toggle(int i,int j,int v)
033 {
034     row[i] ^= (1 << v);
035     col[j] ^= (1 << v);
036     part[belong[i][j]] ^= (1 << v);
037 }
038
039 void init()
040 {
041     int i,j,t;
042     for(t = 0;t < 5;t ++)
043     {
044         for(i = t;i < 9 - t;i ++)
045             for(j = t;j < 9 - t;j ++)
046                 rank[i][j] = 5 + t + 1;
047     }
048     //初始化belong数组
049     markbelong(1,1,1);
050     markbelong(1,4,2);
051     markbelong(1,7,3);
052     markbelong(4,1,4);
053     markbelong(4,4,5);
054     markbelong(4,7,6);
055     markbelong(7,1,7);
056     markbelong(7,4,8);
057     markbelong(7,7,9);
058
059     ecount = initmark = 0;
060     for(i = 0;i < 9;i ++)
061         for(j = 0;j < 9;j ++)
062         {
063             scanf("%d",&board[i][j]);
064             if(board[i][j] == 0)
065             {
066                 empty[ecount].i = i;
067                 empty[ecount].j = j;
068                 ecount ++;
069             }
070             else
071             {
072                 initmark += rank[i][j] * board[i][j]; //计算已经有数组的格子获得的分值
073                 toggle(i,j,board[i][j]);  //标记使用过
074             }
075         }
076 }
077
078 void dfs(int p,long m)
079 {
080     if(p == ecount)
081     {
082         find = 1;
083         if(m > max) max = m;
084         return;
085     }
086     int k;
087     for(k = 1;k <= 9;k ++)
088     {
089         if((((row[empty[p].i] >> k) & 1) == 0) && (((col[empty[p].j] >> k) & 1) == 0) && (((part[belong[empty[p].i][empty[p].j]] >> k) & 1) == 0))
090         {
091             toggle(empty[p].i,empty[p].j,k);
092             dfs(p + 1,m + rank[empty[p].i][empty[p].j] * k);
093             toggle(empty[p].i,empty[p].j,k);
094         }
095     }
096 }
097
098 int main()
099 {
100     init();
101     find = 0;
102     dfs(0,0);
103     if(find)    printf("%ld\n",max + initmark);
104     else    printf("-1\n");  //注意无解情况
105     return 0;
106 }