不是每一行都一定要放旗子。
每放一个棋子,就把列给标记下。因为一行最多放一个棋子。
(不标记,写另一个函数来查找当前这列之前是否放过一个棋子结果T了 = =!)
AC 代码
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,k,s,cnt; int hash[20][20]; char map[20][20]; void Dfs(int x){ for(int i = 0;i < n;i++){ if(cnt == k){ s++; return ; } if(x > n) return; if(map[x][i] == '#'&& !hash[x][i]){ for(int j = x;j < n;j++){ hash[j][i] = 1; } cnt++; Dfs(x + 1); cnt--; for(int j = x;j < n;j++){ hash[j][i] = 0; } } } Dfs(x + 1); } int main(){ while(~scanf("%d%d",&n,&k)){ if(n == -1 && k == -1) break; for(int i = 0;i < n;i++){ scanf("%s",map[i]); } memset(hash,0,sizeof(hash)); s = 0,cnt = 0; Dfs(0); cout<<s<<endl; } return 0; }