POJ 1321-棋盘问题

vj原题链接

题目

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input
输入含有多组测试数据。 
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 
当为-1 -1时表示输入结束。 
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1

与八皇后问题相似

AC代码

#include<stdio.h>
#include<string.h>
#define maxn 1024

int n,k;
int ans,y;
char field[maxn][maxn];
int book[maxn];

void ndfs(int now)
{
    if(k == y)
    {
        ans++;
        return;
    }
    if(now >= n)
        return;
    for(int i = 0;i<n;i++)
    {
        if(book[i] == 0 && field[now][i] == '#')
        {
            book[i] = 1;
            y++;
            ndfs(now+1);
            book[i] = 0;
            y--;
        }
    }
    ndfs(now+1);
}

int main()
{
    while(scanf("%d%d",&n,&k) == 2 && n>= 1 && n <= 8 && k >= 0 && k <= n)
    {
        ans = 0;
        y = 0;
        for(int i = 0;i<n;i++)
        {
            scanf("%s",&field[i]);
        }

        memset(book,0,sizeof(book));
        ndfs(0);


        printf("%d\n",ans);
    }
}

踩坑点

【错误点】在定义全局变量ans和y的同时，为它们初始化为0了

【反思】在设置全局变量的时候，要思考到，在初始化的时候，对下面使用到它们的函数是否会有影响，若有，可以在main函数内再为其赋初值
【错误点】最终ans输出时，格式为printf("%d",ans);,导致Presentation Error

【反思】在进行题目要求的格式输出时，应注意是否要输出\n,本题正确输出为printf(“%d\n”,ans);