棋盘游戏

链接: https://vjudge.net/problem/POJ-1321

题目描述

ac 代码

#include <iostream>
using namespace std;
const int N = 10;

int n, k, ans;
char a[N][N];
int vis_r[N];
// dfs every col
void debug()
{
    for(int i =0;i<n;i++){
        for(int j =0;j<n;j++)
        {
            cout << a[i][j]<<" ";
        }
        cout << endl;
    }
}
void dfs(int now, int total)
{
    if (now > k)
    {
        if (total == k)
            ans++;
        return;
    }

    for (int r = 0; r < n; r++)
    {
        if (vis_r[r])           continue;
        if (a[now][r] != '#')   continue;
        vis_r[r] = 1;
        // cout <<"r" << r << endl;
        dfs(now + 1, total + 1);
        vis_r[r] = 0;
    }
    dfs(now + 1, total);
}
signed main()
{
    while (cin >> n >> k && ~n && ~k)
    {
        memset(vis_r, 0, sizeof vis_r);
        ans = 0;
        for (int c = 0; c < n; c++)
        {
            for (int r = 0; r < n; r++)
            {
                cin >> a[c][r];
            }
        }
        dfs(0, 0);
        cout << ans << endl;
        // memset(a, 0, sizeof a);
    }
}

思路

这个题很经典的搜索题, 但是和皇后游戏不一样, 这个题不是每一行都确定要放棋子的, 所以要搜索两种状态, 一种是该行放棋子, 一种是该行不放棋子.

大概就是

for(列 : 每一列元素) {
      dfs(放棋子, 剩余棋子)
      dfs(不放棋子, 剩余棋子)
}

慢慢的感觉暴搜就是要不重不漏 , 选好枚举办法很重要

这个题看题解了, 不过顺思路也可以理解