A8004.棋盘问题

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放 kk 个棋子的所有可行的摆放方案 CC

输入格式

输入含有多组测试数据。

每组数据的第一行是两个正整数 n,kn,k ,用一个空格隔开,表示了将在一个 n×nn \times n 的矩阵内描述棋盘,以及需要摆放的棋子数目。 (n8,kn)(n \leq 8, k \leq n)

当为−111 −1时表示输入结束。

随后的 nn 行描述了棋盘的形状:每行有 nn 个字符,其中 '#' 表示此位置可放棋子,'.' 表示此位置不可放棋子。

输出格式

对于每一组数据,给出一行输出,输出摆放的方案数目CC (数据保证C<231C < 2^{31})。

输入输出样例

  • 输入#1

    2 1
    #.
    .#
    4 4
    ...#
    ..#.
    .#..
    #...
    -1 -1

    输出#1

    2
    1
首页