uva 639 - Don't Get Rooked

クリックしてリンクを開く
最大4 x 4の碁盤を与えて、碁盤の上に車と壁を代表する「X」を置くことができて、2つの車に対して1本の直線につながってはいけないことを要求して、中間に「X」あるいは2つの連線が折れ線です
解題の構想:1暴力は解空間を列挙して、解空間の最大の値を求めます2遡及法、すべての点の放すか放さないかを探ることを通じて、また条件を満たして最後の最大の値を求めることができるかどうかを判断します
コード1(暴力列挙):

//    2^16  
//                     2 16   ，         ，           ，            。       ，              ，   0 1  （1   ，0    ），           16 ，                ，               ，         ，        ，  n*n   ，    2^(n*n) -1,               1 &  ，           ，                     。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 4;

int n , cnt , pos , ans , flag;
bool  bite[MAXN*MAXN];//      
char G[MAXN][MAXN];//       
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//    

//        
//    'X'    ，  '.' bite  1      0，    1
int judge(int x , int y){
    for(int i = x-1 ; i >= 0  ; i--){
        if(bite[i*n+y] &&G[i][y] == '.')
            return 0;
        if(G[i][y] == 'X')
            break;
    }
    for(int i = x+1 ; i < n  ; i++){
        if(bite[i*n+y] &&G[i][y] == '.')
            return 0;
        if(G[i][y] == 'X')
            break;
    }
    for(int i = y-1 ; i >= 0  ; i--){
        if(bite[x*n+i] &&G[x][i] == '.')
            return 0;
        if(G[x][i] == 'X')
            break;
    }
    for(int i = y+1 ; i < n  ; i++){
        if(bite[x*n+i] &&G[x][i] == '.')
            return 0;
        if(G[x][i] == 'X')
            break;
    }
    return 1;
}
//             
void solve(int num){
    int i , j;
    flag = 0;
    pos = n*n - 1;//pos  bite     
    memset(bite , 0 , sizeof(bite));
    while(pos >= 0){
        bite[pos] = num & 1;//   1&  
        --pos;//    
        num >>= 1;//    
    }
    //      ，  bite   1    
    for(i = 0 ; i < n ; i++){
        for(j = 0 ; j < n ; j++){
            if(bite[i*n+j]){
                if(G[i][j] == 'X')//   'X'    1               
                    return; 
                if(G[i][j] == '.'){//   '.'  
                    if(judge(i , j) == 0)
                        return;
                }
            }
        }
    }
    //            1   
    for(i = 0 ; i < n*n ; i++){
        if(bite[i])
            ++flag;
    }
}

//   
int main(){
    while(scanf("%d%*c" , &n) && n){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++)
                scanf("%c" , &G[i][j]);
            getchar();
        }
        int m = n*n;
        ans = 0;
        cnt = pow(2 , m) - 1;//    
        while(cnt >= 0){//       
            solve(cnt);
            --cnt;
            ans = (ans > flag ? ans : flag);//    ans
        }
        printf("%d
" , ans);
    }
    return 0;
}

コード2(遡及検索):

//         ，        dfs               ，     。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 5;

int n , ans , flag;
char G[MAXN][MAXN];
int vis[MAXN][MAXN]; //   'X'    -1，   0

//        

int judge(int x, int y) {
    for (int i = x - 1; i >= 0; i--) {
        if (vis[i][y] == 1)//   1     
            return 0;
        if (vis[i][y] == -1)//   'X'   
            break;
    }
    for (int i = y - 1; i >= 0; i--) {
        if (vis[x][i] == 1)
            return 0;
        if (vis[x][i] == -1)
            break;
    }
    return 1;
}

//    

void dfs(int i, int j, int max) {
    if (max > ans)
        ans = max;
    while (i < n) {
        if (j<n && G[i][j] == '.' && vis[i][j] == 0) {
            flag = judge(i, j);
            if (flag) {
                vis[i][j] = 1;
                dfs(i, j + 1, max + 1);
                vis[i][j] = 0;
            }
        }
        if (j >= n) {
            ++i;
            j = 0;
        }
        else
            ++j;
    }
}



//   

int main() {
    //freopen("input.txt" , "r" , stdin);
    while (scanf("%d%*c", &n) && n) {
        memset(vis, 0, sizeof (vis));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%c", &G[i][j]);
                if (G[i][j] == 'X') {
                    vis[i][j] = -1; //   vis  
                }
            }
            getchar();
        }
        ans = 0;
        dfs(0, 0, 0); //    （      ）
        printf("%d
", ans);
    }
    return 0;
}