NOIP［靶形数独］深度优先搜索

题解

把当前填的数作为状态DFS，在加上一点剪枝可以卡过去。（不用二进制）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define hc puts("")
using namespace std;
const int All = ( 1<<9 ) - 1;
int fs [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 vis [10] [10] , vh [10] [10] , vl [10] [10] , vk [10] [10] , b [10] [10];
int id ( int h , int l ) {return ((h-1)/3)*3 + ((l-1)/3) + 1 ;
}int ans = 0 ;void dfs () {int upe = 10 ;int x , y ;for ( int i = 1 ; i <= 9 ; ++ i )for ( int j = 1 ; j <= 9 ; ++ j ) if ( vis [i] [j] == 0 ) {int chk = 0 ;for ( int k = 1 ; k <= 9 ; ++ k )if ( !vh [i][k] && !vl [j][k] && !vk [ b [i] [j] ][k] ){chk ++ ;}if ( chk < upe ) {upe = chk ;x = i , y = j ;            }}if ( upe == 10 ){int k = 0 ;for ( int i = 1 ; i <= 9 ; ++ i )for ( int j = 1 ; j <= 9 ; ++ j )k += vis [i] [j] * fs [i] [j] ;ans = max ( ans , k ) ;return ;}if ( upe == 0 ) return;for ( int k = 1 ; k <= 9 ; ++ k ){if ( !vh [x][k] && !vl [y][k] && !vk [ b [x] [y] ][k] ){vh [x] [k] = vl [y] [k] = vk [ b [x] [y] ] [k] = 1;vis [x] [y] = k ;dfs ();vh [x] [k] = vl [y] [k] = vk [ b [x] [y] ] [k] = 0;vis [x] [y] = 0 ; }   }       
}int main () {memset ( vh , 0 , sizeof vh ) ;memset ( vl , 0 , sizeof vl ) ;memset ( vk , 0 , sizeof vk ) ;for ( int i = 1 ; i <= 9 ; ++ i )for ( int j = 1 ; j <= 9 ; ++ j ){scanf ( "%d" , &vis [i] [j] );if ( vis [i] [j] != 0 ){int po = vis [i] [j] ;vh [i] [po] = vl [j] [po] = vk [id(i,j)] [po] = 1;}b [i] [j] = id( i , j ) ;} ans = -1;dfs ();printf ( "%d" , ans );return 0 ;
}