2
1

      （1）编程思路。

      在棋盘问题中，棋子摆放的位置只能是“#”, 且不能同行和同列。由于在深度优先搜索中采用按行递增的顺序来搜索的，这样每次递归下一行，所以每一行不会有冲突，不可能出现同行的情况。只需保证不同列，为判断某一列上是否有其他棋子，可定义一个数组visit[]来保存列的访问状态，visit[i]=true表示第i列上放置有棋子；visit[i]=false表示第i列上未放置棋子。

      （2）源程序。

#include <iostream>

using namespace std;

bool visit[20];

char map[20][20];

int ans,k,n;    // ans表示方案数,k表示棋子数目,n表示棋盘的大小

void DFS(int row,int num)   // 逐行搜索，row为当前搜索行，num为已填充的棋子数

{

    if(num>=k)   // 判断是否棋子已经放完，如果放完，记录方案数加1

    {

        ans++;

        return;

    }

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

    {

        for(int j=0;j<n;j++)

        {

            if(!visit[j] && map[i][j]=='#')  // 如果该列没放棋子且该位置为棋盘，那么在这里放上棋子

            {

                visit[j]=true;             // 标记该列上有棋子

                DFS(i+1,num+1);   // 搜索下一行放下一个棋子

                visit[j]=false;           // 修改标记后递归回来要及时复原

            }

        }

    }

}

int main()

{

       int i;

      while (cin>>n>>k)

      {

          if (n==-1&&k==-1)

              break;

          for (i=0;i<n;i++)

             visit[i]=false;

          for (i=0;i<n;i++)

            cin>>map[i];

        ans=0;

        DFS(0,0);

        cout<<ans<<endl;

    }

    return 0;

}