题目链接：

题目大意：

你有k个棋子，若干个可以填的位置，要求填下一个棋子后其行和列不能填棋子。

思路：

dfs策略

画图理解更好些：

填下一个棋子。行列需要跳一下，dfs的时候for循环代表行，用一个vis数组来表示该列能否用，如果符合条件的需要i+1跳到下一行。

所以for循环第一个可以这样写：

for(int i = x; i < n; ++i)

下面由于用了vis数组，所以从0开始遍历就好。

 

下面是AC代码：

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int MX = 100+5;char mp[MX][MX];int vis[MX];int n, k, ans;void dfs(int x, int y){    if(y >= k)    {        ans++;        return;    }    for(int i = x; i < n; ++i)        for(int j = 0; j < n; ++j)        {            if(mp[i][j] == '#' && !vis[j])            {                vis[j] = 1;                dfs(i+1, y+1);                vis[j] = 0; //回溯， 类似n皇后问题。            }        }    return;}int main(){    while(scanf("%d%d", &n, &k) != EOF && ((n!=-1)&&(k!=-1)))    {        ans = 0;        memset(mp, 0, sizeof(mp));        memset(vis, 0, sizeof(vis));        for(int i = 0; i < n; ++i) scanf("%s", mp[i]);        dfs(0, 0);        printf("%d\n", ans);    }}
        
       
      

如有疑问，欢迎评论指出！