luogu1092[虫食算] 搜索

DFS 从左往右搜+减枝

注意数组越界问题！！！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30 ;

int col [N] ;
int vis [N] ;
char a [3][N] ;
int n;
int id ( char ch ) {
    return ch - 'A' + 1;
}
void dfs ( int li , int ro , int tmp ) {
    if ( li == 0 ) {
        if ( tmp != 0 ) return ;
        for ( int i = 1 ; i <= n ; ++ i ) 
            printf ( "%d " , col [i] );
        exit(0);
    }
    for ( int i = li - 1 ; i >= 1 ; -- i ){
        int w1 = col [ id ( a [0] [i]  ) ] ;
        int w2 = col [ id ( a [1] [i]  ) ] ;
        int w3 = col [ id ( a [2] [i]  ) ] ;
        if ( w1 == -1 || w2 == -1 || w3 == -1 ) continue ;
        if ( (w1 + w2)%n != w3 && ( w1 + w2 + 1 )%n != w3 ) return ;
    }
    if ( col [ id ( a [ro] [li]  ) ] == -1 ) {
        if ( ro != 2 ) {
            for ( int i = n-1 ; i >= 0 ; -- i ) if ( ! vis [i] ) {
                col [ id ( a [ro] [li] ) ] = i ;
                vis [i] = 1;
                dfs ( li , ro + 1 , tmp ) ;
                col [ id ( a [ro] [li] ) ] = -1 ;
                vis [i] = 0;
            }
        }else {
            int x = col [id(a[0][li])] + col [id(a[1][li])] + tmp ;
            if ( vis [x%n] != 0 ) return ;
            vis [x%n] = 1 ;
            col [ id( a [2] [li] ) ] = x%n ;
            dfs ( li-1 , 0 , x/n );
            col [ id( a [2] [li] ) ] = -1 ;
            vis [x%n] = 0 ;
        }
    }else {
        if ( ro != 2 ) 
            dfs ( li , ro+1 , tmp );
        else {
            int x = col [id(a[0][li])] + col [id(a[1][li])] + tmp ;
            if ( col [ id( a [2] [li] ) ] != x % n ) return ;
            dfs ( li-1 , 0 , x / n );
        }
    }
}

int main () {
    memset ( vis , 0 , sizeof vis );
    memset ( col , -1 , sizeof col );
    scanf ( "%d" , &n ) ;getchar();
    for ( int i = 0 ; i < 3 ; ++ i )        
        scanf ( "%s" , a [i] + 1 ) ;

    dfs ( n , 0 , 0 ) ;

    return 0 ;
}