c++ - 回溯——用硬币填充网格

Question

我正在尝试做这个我在查找面试问题时遇到的问题。我们被问及将 r 个硬币放置在 n*m 网格上的方法数量，使得每行和每列至少包含一个硬币。

我想到了一个回溯解决方案，按行主要顺序处理网格中的每个单元格，我已经这样设置了我的递归。似乎我的方法有问题，因为它每次都输出 0。有人可以帮我找到我的方法中的错误。 ？谢谢。

约束。 n , m < 200 且 r < n*m;

这是我想出的代码。

#include<cstdio>
#define N 201
int n, m , r;
int used[N][N];
int grid[N][N] ;  // 1 is coin is placed . 0 otherwise. // -1 undecided.

bool isOk()
{
    int rows[N];
    int cols[N];

    for(int i = 0 ; i < n ; i++) rows[i] = 0;
    for(int i = 0 ; i < m ; i++) cols[i] = 0;
    int sum = 0;
    for(int i = 0 ; i < n ; i++)for(int j = 0; j < m ; j++)
    {
        if(grid[i][j]==1)
        {
            rows[i]++;
            cols[j]++;
            sum++;  
        }
    }
    for(int i = 0 ; i < n ; i++) 
    {
        if(rows[i]==0) return false;
    }

    for(int j = 0 ; j < n ; j++)
    {
        if(cols[j]==0) return false;
    }
    if(sum==r) return true;
    else return false;
}

int calc_ways(int row , int col,  int coins)
{
    if(row >= n) return 0;
    if(col >= m) return 0;
    if(coins > r) return 0;
    if(coins == r) 
    {
        bool res = isOk();
        if(res) return 1; 
        else 0;
    }

    if(row == n - 1 and col== m- 1) 
    {
        bool res = isOk();
        if(res) return 1;
        else return 0;
    }

    int nrow, ncol;

    if(col + 1 >= m)
    {
        nrow = row + 1;
        ncol = 0;
    }
    else
    {
        nrow = row;
        ncol = col + 1;
    }
    if(used[row][col]) return calc_ways(nrow, ncol, coins);
    int ans =  0;
    used[row][col] = 1;
    grid[row][col] = 0;
    ans += calc_ways(nrow , ncol , coins);

    grid[row][col] = 1;
    ans += calc_ways(nrow , ncol , coins + 1);

    return ans;
}

int main()
{
    int t;
    scanf("%d" , &t);
    while(t--)
    {
        scanf("%d %d %d" , &n , &m , &r);
        for(int i = 0 ; i <= n ; i++)
        {
            for(int j = 0; j <= m ; j++)
            {
                used[i][j] = 0;
                grid[i][j] = -1;
            }
        }
        printf("%d\n" , calc_ways(0  ,  0 , 0 ));
    }
    return 0;
}

Answer 1

你几乎不需要一个程序来解决这个问题。

不失一般性，设m <= n。

首先，我们必须有 n <= r，否则无解。

然后，我们将问题 segmentation 为一个大小为 m x m 的正方形，我们将在其上沿主对角线放置 m 个硬币，以及一个余数，在其上放置 n - m 个硬币以满足剩余条件.

有一种方法可以沿着正方形的主对角线放置硬币。

余数有 m^(n - m) 种可能性。我们可以在 n!方式，尽管其中一些将是重复的(剩下多少作为学生的练习)。

此外，还有 r - n 个硬币可以放置，还有 (m - 1)n 个地方可以放置。

将所有这些放在一起我们有一个上限

1 x m^(n - m) x n! x C((m - 1)n, r - n)

问题的解决方案。将此数字除以重复排列的数量即可完成。