3037: 棋盘问题 c++ 标准dfs

解题思路:
1.标记棋盘位置

2.每个位置可以放棋子和不放棋子

3.分别搜索

4.填完一种可能ans+1
注意事项:
dfs中有两个量，要区分！！

step表示在第几号棋盘格

num表示填了几个棋子
参考代码:

#include <bits/stdc++.h>
using namespace std;
char c[100][100];
int n,k;
int ans;
struct dir
{
    int x;
    int y;
}d[1001];
int p = 1;
bool vis[100][100];
void init()
{
    p = 1;
    ans = 0;
    for(int i = 0; i <= 1000; i++)
    d[i].x = d[i].y = 0;
    memset(vis,0,sizeof(vis));
    n = k = 0;
    memset(c,'EOF',sizeof(c));
}
void read()
{
    scanf("%d%d",&n,&k);
    if(n == -1 && k == -1) exit(0);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            cin >> c[i][j];
            if(c[i][j] == '#')
            d[p].x = i,
            d[p].y = j,
            p++;
        }
}
bool check(int dx,int dy)
{
//检查横列  
    for(int i = 1; i <= n; i++)
        if(i != dy && vis[dx][i])
            return false;
    for(int i = 1; i <= n; i++)
        if(i != dx && vis[i][dy])
            return false;
    return true;
}
void dfs(int step,int num)
{
    if(num == k+1)
    {
        ans++;
        return;
    }
    if(num > k+1) return;
    if(step > p-1) return;
    dfs(step+1,num);
    if(check(d[step].x,d[step].y) && !vis[d[step].x][d[step].y])
    {
        vis[d[step].x][d[step].y] = true;
        dfs(step+1,num+1);
        vis[d[step].x][d[step].y] = false;
    }
}
int main()
{
    while(1)
    {
        init();
        read();
        dfs(1,1);
        printf("%d\n",ans);
    }
    return 0;
}