1

我试图回答我在查找面试问题时遇到的这个问题。我们被问到将 r 个硬币放置在一个 *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;
}
4

3 回答 3

3

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

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

首先，我们必须有 n <= r，否则没有解决方案是可能的。

然后，我们将问题细分为一个大小为 mxm 的正方形，我们将在其上沿主对角线放置 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)

问题的解决方案。将此数字除以重复排列的数量，您就完成了。

于 2012-07-24T23:07:30.577 回答
0

问题 1

代码将首先在每个方格上放置一枚硬币并将每个方格标记为已使用。

然后它将测试最终位置并确定最终位置不符合 r 个硬币的目标。

接下来它将开始回溯，但永远不会真正尝试另一个选择，因为 used[row][col] 设置为 1，这会使代码短路以放置硬币。

换句话说，一个问题是“已使用”中的条目被设置，但在递归期间从未被清除。

问题 2

代码的另一个问题是，如果 n,m 的大小为 200，则它永远不会完成。

问题是这个回溯代码的复杂度为 O(2^(n*m))，因为它将尝试放置硬币的所有可能组合（n=m=200 的许多宇宙生命周期......）。

我建议你看看不同的方法。例如，您可能需要考虑动态规划来计算将“k”个硬币放置在棋盘剩余的“a”列上的方式，这样我们就可以确保将硬币放置在棋盘的“b”行上。目前没有硬币的棋盘。

于 2012-07-23T18:38:15.527 回答
0

它可以被视为可以用 r 个硬币填充 d 网格的总方式 - （留下单行和填充 d 剩余的总方式 - 留下单列和填充 d 剩余的总方式 - 留下行和列的总方式一起 nd 填充 d 休息）这意味着

p(n*m ,r) -( (p((n-1)*m , r) * c(n,1)) +(p((m-1)*n , r) * c(m,1))+(p((n-1)*(m-1) , r) * c(n,1)*c(m,1)) )

我只是这么认为，但不确定！

于 2012-12-26T09:01:24.120 回答