454 / 1008 Problem A POJ 1321 棋盘问题
d.在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
s.dfs
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; char cb[10][10];//棋盘 int col[10];//标记当前列是否有棋子 int ans,n,k;//ans 记录方案总数 void dfs(int row,int sum){//行,已放置的总数 if(sum==k){//已摆放的棋子总数 等于 k ans++; return; } int i,j; for(i=row;i<n;i++){//遍历行,从没有放置棋子的row行开始遍历 for(j=0;j<n;j++){//遍历列,从第一列开始遍历 if(cb[i][j]=='#'&&!col[j]){//棋盘区域,并且当前列没有棋子 col[j]=1; dfs(i+1,sum+1);//在下一行中寻找放置棋子的位置 col[j]=0;//取消标记 } } } } int main(){ int i; while(~scanf("%d%d",&n,&k)){ if(n==-1&&k==-1)break; ans=0;//方案总数 memset(col,0,sizeof(col));//标记初始化 memset(cb,'