// 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子 ... 其中 # 表示棋盘区域
// （数据保证不出现多余的空白行或者空白列）// 只能在棋盘'#'上面放棋子 但棋盘形状不一定规则// 法 01
#include<bits/stdc++.h>
using namespace std;char chess[10][10]; // 记录 棋盘
bool used[10]; // 记录 第 i 列上 是否存在棋子
int ans; // 记录 方案数
int used_all; // 记录 已摆放棋子的总数int n,k;void dfs( int a ) // 第 a 行
{if( used_all==k ) { ans++; return ; } // 摆放k个棋子的所有可行的摆放方案if( a>=n ) return ; // 搜过头了for( int i=0;i<n;i++ ){// 第 i 列未放棋子 且该位置为棋盘部分 // 当时理解有误if( used[i]==false && chess[a][i]=='#' ) {used[i]=true; used_all++; // 路径标记dfs( a+1 );used[i]=false; used_all--;}}dfs( a+1 ); // 再深搜 当且仅当 第 a 行 无棋盘部分 // 由于未标记 第 a 行 所以不会出现重复计数
}int main()
{while( ~scanf("%d%d",&n,&k) ){if( n==-1 && k==-1 ) break; // 当为-1 -1时表示输入结束// initans=used_all=0;memset( chess,0,sizeof( chess ) );memset( used,0,sizeof( used ) );for( int i=0;i<n;i++ ) scanf("%s",chess[i]);dfs( 0 );printf("%d\n",ans);}return 0;
}
// 法 02
#include<bits/stdc++.h>
using namespace std;char chess[10][10]; // 检测数组类型
bool used[10];
int n,k,ans;void dfs( int a,int cnt ) // 第 a 行 第 cnt 个棋子
{if( cnt==k ) { ans++; return ; }int i,j;for( i=a;i<n;i++ ) // 行{for( j=0;j<n;j++ ) // 列{if( used[j]==false && chess[i][j]=='#' ){used[j]=true;dfs( i+1,cnt+1 );used[j]=false;}}}
}int main()
{while( ~scanf("%d%d",&n,&k) ){if( n==-1 && k==-1 ) break;ans=0;memset( chess,0,sizeof( chess ) );memset( used,0,sizeof( used ) );for( int i=0;i<n;i++ ) scanf("%s",chess[i]);dfs( 0,0 );printf("%d\n",ans);}return 0;
}
//
find:
01 row 行 column 列
02 鬼使神差 题目理解错了 可能因为状态不佳
03 控制变量法 减少一个维度进行遍历
04 检测数组类型 ( 找挺久的其实 )