题目就不赘述了,很基本的dfs画树思路的题,然而却做了很久,恨只恨自己只会死套紫书内容而不灵活  例如我一直想用C[row]去存储第row行棋子放在第几列,但其实不用这么麻烦只要用C[j]去存储第j列是否已经有棋子放了,不过我觉得这个地方倒不是什么大问题。

对于本题,最重要最重要的总结就是 在dfs画树的时候:

dfs()

{

for(xxxxxx)

{

blabla            // 操作1们

dfs(xx+xx)

这个地方是重点一定要把操作1们还回去!!!!!!!!

}

为什么要有这个归还的操作?

因为dfs画树对吧,你虽然觉得是个平行世界,但是在这个for循环的过程中,它是先画完前面的枝子(虽然这个枝子可能长可能短)再去画后面的 你怎么能让1枝的第5层去影响2枝的第4层的数据呢?对吧,其实很简单= =

下面贴代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char map[10][10];

int C[10];
int n,k;
int ans;


void dfs(int row)
{

    if(k==0 )                //显  递归边界
    {
    ans++;
    return;
    }
    if(row>=n) return;    //隐  递归边界    

    for(int j=0;j<n;j++)
        if(C[j]==0 &&     map[row][j]=='#')
        {
        C[j]=1;
        k--;
        dfs(row+1);
        C[j]=0;        //就是这,一定记得要还回去!
        k++;
         }
    dfs(row+1);            //而且注意不要忘记无法放棋子的地方继续向下dfs哦
}

int main()
{
    int i;
    int k1=k;
    while(scanf("%d%d",&n,&k)&& n!=-1 &&k!=-1)
    {
            ans=0;
        int k=k1;

        for( i=0; i<n; i++)
            scanf("%s",&map[i]);

        memset(C,0,sizeof(C));

    dfs(0);
    printf("%d\n",ans);

    }
    return 0;
}

唉,这么简单的dfs水题我却还需wa几遍才过= =、,总之多多练习吧,熟能生巧,我觉得算法亦然,总之我期望的是能每日一题,基本是照着kuangbin带你飞的题目顺序吧(?),这也就是day1的题目啦,继续加油叭!

02-10 20:38