poj1321 棋盘问题

要求在不规则棋盘上摆放K个棋子,使得横竖行列上都只有唯一的一颗棋子,求出有多少种摆法。

建立一个n*n的区域,记录可以放棋子的地方,然后进行搜索,求出满足要求的方法,用的是深度优先搜索

#include<stdio.h>
#include<string.h>

int lines;//行(列)数
int chess_num;//摆放的棋子数
int count;//计数器
int placed_num;//当前已摆放的棋子
char board[9][9];//棋盘
char visit[9];//列标记

void dfs(int i){
    int j;    
    if(placed_num == chess_num){
        count++;
        return;
    }
    if(i>=lines)
        return;
    for(j=0;j<lines;j++){
        if(board[i][j] == '#' && visit[j]=='0'){//当前行可以摆放棋子,则尝试摆放
            placed_num++;
            visit[j]='1';
            dfs(i+1);
            placed_num--;
            visit[j]='0';
        }
    }
    dfs(i+1);
}


void main(){
    int i,j;
    scanf("%d %d",&lines,&chess_num);
    while(lines != -1 && chess_num != -1){
        getchar();
        memset(board,'\0',sizeof(board));
        for(i=0;i<lines;i++){        
            for(j=0;j<lines;j++)
                scanf("%c",&board[i][j]);
            getchar();
        }
        memset(visit,'0',sizeof(visit));
    count=0;
    placed_num=0;
    dfs(0);
    printf("%d\n",count);
        scanf("%d %d",&lines,&chess_num);
    }
}
gerrard wechat
微信扫一扫,订阅我的博客动态^_^
您的支持将鼓励我继续创作!