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

题解

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define hc puts("")
using namespace std;
const int All = ( << ) - ;
int fs [] [] = {
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,  ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , },
    { ,  ,  ,  ,  ,   ,  ,  ,  , }
};

int vis [] [] , vh [] [] , vl [] [] , vk [] [] , b [] [];
int id ( int h , int l ) {
    return ((h-)/)* + ((l-)/) +  ;
}

int ans =  ;

void dfs () {
    int upe =  ;
    int x , y ;
    for ( int i =  ; i <=  ; ++ i )
        for ( int j =  ; j <=  ; ++ j ) if ( vis [i] [j] ==  ) {

            int chk =  ;
            for ( int k =  ; k <=  ; ++ 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 ==  ){
        int k =  ;
        for ( int i =  ; i <=  ; ++ i )
            for ( int j =  ; j <=  ; ++ j )
                k += vis [i] [j] * fs [i] [j] ;
        ans = max ( ans , k ) ;
        return ;
    }
    if ( upe ==  ) return;
    for ( int k =  ; k <=  ; ++ k ){
        if ( !vh [x][k] && !vl [y][k] && !vk [ b [x] [y] ][k] ){
            vh [x] [k] = vl [y] [k] = vk [ b [x] [y] ] [k] = ;
            vis [x] [y] = k ;
            dfs ();
            vh [x] [k] = vl [y] [k] = vk [ b [x] [y] ] [k] = ;
            vis [x] [y] =  ; 
        }   
    }       
}

int main () {
    memset ( vh ,  , sizeof vh ) ;
    memset ( vl ,  , sizeof vl ) ;
    memset ( vk ,  , sizeof vk ) ;
    for ( int i =  ; i <=  ; ++ i )
        for ( int j =  ; j <=  ; ++ j ){
            scanf ( "%d" , &vis [i] [j] );
            if ( vis [i] [j] !=  ){
                int po = vis [i] [j] ;
                vh [i] [po] = vl [j] [po] = vk [id(i,j)] [po] = ;
            }
            b [i] [j] = id( i , j ) ;
        } 
    ans = -;
    dfs ();
    printf ( "%d" , ans );
    return  ;
}