CODEWITHSUNDEEP
cdynamic-programming
MyGanton
MyGanton

Reputation: 37

Minimum number of squares to tile the rectanlge in C

The task:

Assume a rectangle of size n × m. Determine the minimum number of squares that is required to tile the rectangle.

I tried the following:

#include <stdlib.h>
#include <math.h>
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

int matrix(int n, int m)
{
    int dp[n+1][m+1];

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j] = INFINITY;
        }
    }

    return MinSquare(n, m, dp);
}

int MinSquare(int n, int m, int dp[n][m])
{
    int horizontalMin = INFINITY;
    int verticalMin = INFINITY;

    if(n==m)
    {
        dp[m][n] = 1;
        return 1;
    }
    if(dp[n][m] != INFINITY)
    {
        return dp[n][m];
    }
    for(int i=1;i<=n;i++)
    {
        verticalMin = MIN(MinSquare(i,m,dp)+ MinSquare(n-i,m,dp), horizontalMin);
    }
    for(int i=1;i<=m;i++)
    {
        horizontalMin = MIN(MinSquare(n,i,dp)+MinSquare(n,m-i,dp), horizontalMin);
    }
    dp[n][m] = MIN(verticalMin, horizontalMin);

    return dp[n][m];
}

int main()
{
    printf("%d", matrix(3,4));
    return 0;
}

This results in 2147483647 and I don't see why my code doesn't run correctly.

Any hints?

Upvotes: 0

Views: 160

Answers (1)

Socowi
Socowi

Reputation: 27215

Here are two grave problems. There are probably more than that, but these give you a good start.

Problem 1

INFINITY is a special value for float. The C standard does not define the behavior of assigning int anyIntVar = INFINITY, and it should not be used.

A possible fix is to use INT_MAX (defined in <limits.h>) instead of INFINITY.

Problem 2

verticalMin = MIN(MinSquare(i,m,dp)+ MinSquare(n-i,m,dp), horizontalMin);

should be

verticalMin = MIN(MinSquare(i,m,dp)+ MinSquare(n-i,m,dp), verticallMin);

Upvotes: 2

Related Questions