Tutorialspoint.dev

Count the number of ways to tile the floor of size n x m using 1 x m size tiles

Given a floor of size n x m and tiles of size 1 x m. The problem is to count the number of ways to tile the given floor using 1 x m tiles. A tile can either be placed horizontally or vertically.
Both n and m are positive integers and 2 < = m.

Examples:

Input : n = 2, m = 3
Output : 1
Only one combination to place 
two tiles of size 1 x 3 horizontally
on the floor of size 2 x 3. 

Input :  n = 4, m = 4
Output : 2
1st combination:
All tiles are placed horizontally
2nd combination:
All tiles are placed vertically.


This problem is mainly a more generalized approach to the Tiling Problem.
Approach: For a given value of n and m, the number of ways to tile the floor can be obtained from the following relation.

            |  1, 1 < = n < m
 count(n) = |  2, n = m
            | count(n-1) + count(n-m), m < n
             

C++

// C++ implementation to count number of ways to
// tile a floor of size n x m using 1 x m tiles
#include <bits/stdc++.h>
  
using namespace std;
  
// function to count the total number of ways
int countWays(int n, int m)
{
  
    // table to store values
    // of subproblems
    int count[n + 1];
    count[0] = 0;
  
    // Fill the table upto value n
    for (int i = 1; i <= n; i++) {
        // recurrence relation
        if (i > m)
            count[i] = count[i - 1] + count[i - m];
  
        // base cases
        else if (i < m)
            count[i] = 1;
  
        // i = = m
        else
            count[i] = 2;
    }
  
    // required number of ways
    return count[n];
}
  
// Driver program to test above
int main()
{
    int n = 7, m = 4;
    cout << "Number of ways = "
         << countWays(n, m);
    return 0;
}

Java

// Java implementation to count number
// of ways to tile a floor of size
// n x m using 1 x m tiles
import java.io.*;
  
class GFG {
    // function to count the total number of ways
    static int countWays(int n, int m)
    {
        // table to store values
        // of subproblems
        int count[] = new int[n + 1];
        count[0] = 0;
  
        // Fill the table upto value n
        int i;
        for (i = 1; i <= n; i++) {
            // recurrence relation
            if (i > m)
                count[i] = count[i - 1] + count[i - m];
  
            // base cases
            else if (i < m)
                count[i] = 1;
  
            // i = = m
            else
                count[i] = 2;
        }
  
        // required number of ways
        return count[n];
    }
  
    // Driver program
    public static void main(String[] args)
    {
        int n = 7;
        int m = 4;
        System.out.println("Number of ways = "
                           + countWays(n, m));
    }
}
  
// This code is contributed by vt_m.

Python3

# Python implementation to
# count number of ways to 
# tile a floor of size n x m
# using 1 x m tiles
  
def countWays(n, m):
      
    # table to store values
    # of subproblems
    count =[]
    for i in range(n + 2):
        count.append(0)
    count[0] = 0
      
    # Fill the table upto value n
    for i in range(1, n + 1):
      
        # recurrence relation
        if (i > m):
            count[i] = count[i-1] + count[i-m]
          
        # base cases 
        elif (i < m): 
            count[i] = 1
  
        # i = = m 
        else:
            count[i] = 2
      
      
    # required number of ways
    return count[n]
  
  
# Driver code
  
n = 7
m = 4
  
print("Number of ways = ", countWays(n, m))
  
# This code is contributed
# by Anant Agarwal.

C#

// C# implementation to count number
// of ways to tile a floor of size
// n x m using 1 x m tiles
using System;
  
class GFG {
  
    // function to count the total
    // number of ways
    static int countWays(int n, int m)
    {
  
        // table to store values
        // of subproblems
        int[] count = new int[n + 1];
        count[0] = 0;
  
        // Fill the table upto value n
        int i;
        for (i = 1; i <= n; i++) {
            // recurrence relation
            if (i > m)
                count[i] = count[i - 1]
                           + count[i - m];
  
            // base cases
            else if (i < m)
                count[i] = 1;
  
            // i = = m
            else
                count[i] = 2;
        }
  
        // required number of ways
        return count[n];
    }
  
    // Driver program
    public static void Main()
    {
        int n = 7;
        int m = 4;
  
        Console.Write("Number of ways = "
                      + countWays(n, m));
    }
}
  
// This code is contributed by parashar.

PHP

<?php
// PHP implementation to count 
// number of ways to tile a 
// floor of size n x m using 
// 1 x m tiles
  
// function to count the 
// total number of ways
function countWays($n, $m)
{
      
    // table to store values
    // of subproblems
    $count[0] = 0;
      
    // Fill the table 
    // upto value n
    for ($i = 1; $i <= $n; $i++)
    {
          
        // recurrence relation
        if ($i > $m)
            $count[$i] = $count[$i - 1] + 
                         $count[$i - $m];
          
        // base cases 
        else if ($i < $m
            $count[$i] = 1;
  
        // i = = m 
        else
            $count[$i] = 2;
    }
      
    // required number of ways
    return $count[$n];
}
  
    // Driver Code
    $n = 7;
    $m = 4;
    echo "Number of ways = ", countWays($n, $m);
  
// This code is contributed by ajit
?>


Output:



Number of ways = 5

Time Complexity: O(n)
Auxiliary Space: O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter