poj 1321 简单深搜题解

题意

输入

1.多组测试数据
2.每组数据的第一行是两个正整数，n，k表示了将在一个n*n的矩阵，k枚棋子。
3.输入-1 -1时表示输入结束。
4.每行有n个字符，其中 # 表示棋盘区域，. 表示空白区域。

输出

对于每一组数据，给出一行输出，输出摆放的方案数

样例

输入

-2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

输出

2
1

题目分析

整体是一个不用剪枝的dfs
结束dfs的条件是棋子数用完，或数值超过写入数组的边界。

if(cnt==k)
{
    sum++;
    return ;
}
if(x>n)
    return ;

我们用x代表行，vis[ j ]表示列是否放过棋子
vis[ j ]=1，本列已有棋子；
vis[ j ]=0，本列没有棋子。
在本区域合法，且没有棋子的情况下，想讨论完整所有情况，我们发现：
（1）我们根据顺序，在第j列放入棋子，则vis[ j ]置为1，进入dfs(x+1,cnt+1)，以此进入下一层搜索，搜索不断深入，直到遇到判断条件。之后vis[ j ]被回溯为0，进入下一列。（每一列的情况基本相同）。
（2）对于第x行的所有列，我们都不放入棋子，则执行for循环外的dfs(x+1,cnt)
以下是dfs的核心代码：

for(int j=0;j<n;j++)
{
        if(mp[x][j]=='#'&&vis[j]==0)
        {
            vis[j]=1;
            dfs(x+1,cnt+1);
            vis[j]=0;//回溯
        }
 }
 dfs(x+1,cnt);

完整的ac代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,k;
char mp[10][10];
int vis[10];
int sum=0;
void dfs(int x,int cnt)//x为当前行，cnt为当前摆放的棋子数
{
    if(cnt==k)
    {
        sum++;
        return ;
    }
    if(x>n)
        return ;
    for(int j=0;j<n;j++)
    {
        if(mp[x][j]=='#'&&vis[j]==0)
        {
            vis[j]=1;
            dfs(x+1,cnt+1);
            vis[j]=0;
        }
    }
    dfs(x+1,cnt);
}
int main(void)
{
    while(cin>>n>>k)
    {
        if(n==-1&&k==-1)
            break;
        else
        {
            memset(vis,0,sizeof(vis));sum=0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                    cin>>mp[i][j];
                getchar();
            }
            dfs(0,0);
            cout<<sum<<endl;
        }
    }
    return 0;
}