poj - 1321 - 棋盘问题

题意：在一个n*n的棋盘上放k个棋子有几种放法。(n <= 8, k <= n)

——>>和八皇后问题很像，只是这里不用每行都有，简单回溯。

[cpp]
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 10;
int cnt, n, k;
char MAP[maxn][maxn];
bool vis[maxn];

void dfs(int x, int cur)
{
    if(cur == k)
    {
        cnt++;
        return;
    }
    else
    {
        for(int i = x; i < n; i++)
            for(int j = 0; j < n; j++)
            if(MAP[i][j] == '#' && !vis[j])
            {
                vis[j] = 1;
                dfs(i+1, cur+1);
                vis[j] = 0;
            }
    }
}

int main()
{
    int i, j;
    while(scanf("%d%d", &n, &k) == 2)
    {
        if(n == -1 && k == -1) return 0;
        for(i = 0; i < n; i++)
        {
            getchar();
            for(j = 0; j < n; j++)
                MAP[i][j] = getchar();
        }
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        dfs(0, 0);
        printf("%d\n", cnt);
    }
    return 0;
}

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 10;
int cnt, n, k;
char MAP[maxn][maxn];
bool vis[maxn];

void dfs(int x, int cur)
{
    if(cur == k)
    {
        cnt++;
        return;
    }
    else
    {
        for(int i = x; i < n; i++)
            for(int j = 0; j < n; j++)
            if(MAP[i][j] == '#' && !vis[j])
            {
                vis[j] = 1;
                dfs(i+1, cur+1);
                vis[j] = 0;
            }
    }
}

int main()
{
    int i, j;
    while(scanf("%d%d", &n, &k) == 2)
    {
        if(n == -1 && k == -1) return 0;
        for(i = 0; i < n; i++)
        {
            getchar();
            for(j = 0; j < n; j++)
                MAP[i][j] = getchar();
        }
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        dfs(0, 0);
        printf("%d\n", cnt);
    }
    return 0;
}

补充：软件开发 , C++ ,