CSES Solutions – Counting Tilings
Give an n x m grid, the task is to count the number of ways you can fill an n x m grid using 1 x 2 and 2 x 1 tiles. Output the number of ways modulo 109 + 7.
Examples:
Input: n=2, m=2
Output: 2Input: n=4, m=7
Output: 781
Approach:
The idea is to solve the problem using DP with bitmasking. We’ll process the grid cells column-by-column and since the number of rows can be at max 10, we can use bitmasking only on columns. It can also be observed that while filling a particular column, if we place a (1×2) tile at a cell of one column, the cell of that corresponding row in the next column also gets tiled. So now let’s define our dp state:
dp[i][mask] = number of ways to fill the remaining grid from ith column to mth column such that the ith column arrangement due to (i-1)th column is represented by mask.
Now while filling the ith column we can apply the following strategy. Since some of the cells of the current columns are already filled due to previous column, we will fill only those cells which are empty. Now for the cell (j, i) if it is empty, we can fill it using a 1×2 tile or using a 2×1 tile if cell (j+1,i) is also empty. If we are using a 1×2 tile, it is also filling the corresponding row of next column, so we have to make sure that we are updating the mask for the column (i+1) accordingly while filling the ith column. Also we have to make sure when all the columns are filled then the mask generated for the next column is 0, otherwise that won’t be a valid way to fill the grid.
Follow the steps to solve the problem:
- CountWays function recursively function computes the number of ways to fill the grid using dynamic programming with bitmasking, where
i represents the
Current column being processed andmask represents
current mask representing the state of filled cells in the current column. - For each column I it does the following:
- If
i
reachesm
, check if the entire grid is filled (mask == 0
). Return 1 if true, otherwise return 0. - If the result for the current state is already computed, return it.
- Generate next possible masks for the current column using
generateNextMask,
this function generates the next possible mask based on the current mask and position in the grid by doing the following:- If
j
reachesn
, add thenew_mask
to thenextMask
vector. - If there is enough space and cells are empty, place a 2×1 tile, and move to the next empty cell.
- If the current cell is empty, place a 1×2 tile, and move to the next cell.
- If the current cell is already filled, move to the next cell.
- If
- Iterate over all possible next masks and recursively compute the number of ways.
- Memoize the result for the current state and return it.
- If
- Returns the total number of ways to fill the grid starting from column
i
with the givenmask
.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// dp array to memoize results of subproblems
ll dp[1050][2050]; // dp[i][mask] stores the number of ways to fill the grid starting from column i with the mask representing the current state of filled cells
const int MOD = 1e9 + 7;
// Function to generate the next possible mask based on the current mask and position
void generateNextMask(int n, int curr_mask, int new_mask, int j, vector<int> &nextMask)
{
if (j == n)
{
nextMask.push_back(new_mask);
return;
}
// If there's enough space and cells are empty, place a 2x1 tile
if (j + 1 < n && (((1 << j) & (curr_mask)) == 0) && (((1 << (j + 1)) & (curr_mask)) == 0))
{
generateNextMask(n, curr_mask, new_mask, j + 2, nextMask);
}
// Place a 1x2 tile if the cell is empty
if ((((1 << j) & (curr_mask)) == 0))
{
generateNextMask(n, curr_mask, new_mask + (1 << j), j + 1, nextMask);
}
// Move to the next cell if the current cell is already filled
if ((((1 << j) & (curr_mask)) != 0))
{
generateNextMask(n, curr_mask, new_mask, j + 1, nextMask);
}
}
// Recursive function to compute the number of ways to fill the grid
ll countWays(int n, int m, int i, int mask)
{
// Base case: reached the end of the grid
if (i == m)
{
// If the entire grid is filled, return 1, otherwise return 0
if (mask == 0)
return 1;
else
return 0;
}
// If the result for the current state is already computed, return it
if (dp[i][mask] != -1)
return dp[i][mask];
// Generate next possible masks for the current column
vector<int> nextMask;
generateNextMask(n, mask, 0, 0, nextMask);
// Initialize the answer for the current state
long long ans = 0;
// Iterate over all possible next masks and recursively compute the answer
for (auto x : nextMask)
{
ans = (ans % MOD + countWays(n, m, i + 1, x) % MOD) % MOD;
}
// Memoize the result and return it
dp[i][mask] = ans;
return dp[i][mask];
}
// Driver Code
int main()
{
ll n=2, m=2;
// Initialize dp array with -1
memset(dp, -1, sizeof(dp));
// Compute and print the number of ways to fill the grid
cout << countWays(n, m, 0, 0) << endl;
return 0;
}
import java.util.*;
public class Main {
// dp array to memoize results of subproblems
static long[][] dp = new long[1050][2050]; // dp[i][mask] stores the number of ways to fill the grid starting from column i with the mask representing the current state of filled cells
static final int MOD = (int)1e9 + 7;
// Function to generate the next possible mask based on the current mask and position
static void generateNextMask(int n, int curr_mask, int new_mask, int j, ArrayList<Integer> nextMask) {
if (j == n) {
nextMask.add(new_mask);
return;
}
// If there's enough space and cells are empty, place a 2x1 tile
if (j + 1 < n && ((1 << j & curr_mask) == 0) && ((1 << (j + 1) & curr_mask) == 0)) {
generateNextMask(n, curr_mask, new_mask, j + 2, nextMask);
}
// Place a 1x2 tile if the cell is empty
if ((1 << j & curr_mask) == 0) {
generateNextMask(n, curr_mask, new_mask + (1 << j), j + 1, nextMask);
}
// Move to the next cell if the current cell is already filled
if ((1 << j & curr_mask) != 0) {
generateNextMask(n, curr_mask, new_mask, j + 1, nextMask);
}
}
// Recursive function to compute the number of ways to fill the grid
static long countWays(int n, int m, int i, int mask) {
// Base case: reached the end of the grid
if (i == m) {
// If the entire grid is filled, return 1, otherwise return 0
if (mask == 0)
return 1;
else
return 0;
}
// If the result for the current state is already computed, return it
if (dp[i][mask] != -1)
return dp[i][mask];
// Generate next possible masks for the current column
ArrayList<Integer> nextMask = new ArrayList<>();
generateNextMask(n, mask, 0, 0, nextMask);
// Initialize the answer for the current state
long ans = 0;
// Iterate over all possible next masks and recursively compute the answer
for (int x : nextMask) {
ans = (ans % MOD + countWays(n, m, i + 1, x) % MOD) % MOD;
}
// Memoize the result and return it
dp[i][mask] = ans;
return dp[i][mask];
}
// Driver Code
public static void main(String[] args) {
int n = 2, m = 2;
// Initialize dp array with -1
for (long[] row : dp)
Arrays.fill(row, -1);
// Compute and print the number of ways to fill the grid
System.out.println(countWays(n, m, 0, 0));
}
}
MOD = 10**9 + 7
# Function to generate the next possible mask based on the current mask and position
def generateNextMask(n, curr_mask, new_mask, j, nextMask):
if j == n:
nextMask.append(new_mask)
return
# If there's enough space and cells are empty, place a 2x1 tile
if j + 1 < n and ((1 << j) & curr_mask) == 0 and ((1 << (j + 1)) & curr_mask) == 0:
generateNextMask(n, curr_mask, new_mask, j + 2, nextMask)
# Place a 1x2 tile if the cell is empty
if (1 << j) & curr_mask == 0:
generateNextMask(n, curr_mask, new_mask + (1 << j), j + 1, nextMask)
# Move to the next cell if the current cell is already filled
if (1 << j) & curr_mask != 0:
generateNextMask(n, curr_mask, new_mask, j + 1, nextMask)
# Recursive function to compute the number of ways to fill the grid
def countWays(n, m, i, mask, dp):
# Base case: reached the end of the grid
if i == m:
# If the entire grid is filled, return 1, otherwise return 0
if mask == 0:
return 1
else:
return 0
# If the result for the current state is already computed, return it
if dp[i][mask] != -1:
return dp[i][mask]
# Generate next possible masks for the current column
nextMask = []
generateNextMask(n, mask, 0, 0, nextMask)
# Initialize the answer for the current state
ans = 0
# Iterate over all possible next masks and recursively compute the answer
for x in nextMask:
ans = (ans + countWays(n, m, i + 1, x, dp)) % MOD
# Memoize the result and return it
dp[i][mask] = ans
return ans
# Driver Code
def main():
n = 2
m = 2
# Initialize dp array with -1
dp = [[-1] * (1 << n) for _ in range(m)]
# Compute and print the number of ways to fill the grid
print(countWays(n, m, 0, 0, dp))
if __name__ == "__main__":
main()
// Function to generate the next possible mask based on the current mask and position
function generateNextMask(n, curr_mask, new_mask, j, nextMask) {
if (j === n) {
nextMask.push(new_mask);
return;
}
// If there's enough space and cells are empty, place a 2x1 tile
if (j + 1 < n && (((1 << j) & curr_mask) === 0) && (((1 << (j + 1)) & curr_mask) === 0)) {
generateNextMask(n, curr_mask, new_mask, j + 2, nextMask);
}
// Place a 1x2 tile if the cell is empty
if (((1 << j) & curr_mask) === 0) {
generateNextMask(n, curr_mask, new_mask + (1 << j), j + 1, nextMask);
}
// Move to the next cell if the current cell is already filled
if (((1 << j) & curr_mask) !== 0) {
generateNextMask(n, curr_mask, new_mask, j + 1, nextMask);
}
}
// Recursive function to compute the number of ways to fill the grid
function countWays(n, m, i, mask, dp) {
// Base case: reached the end of the grid
if (i === m) {
// If the entire grid is filled, return 1, otherwise return 0
if (mask === 0)
return 1;
else
return 0;
}
const MOD = 1e9 + 7; // Define MOD constant
// If the result for the current state is already computed, return it
if (dp[i][mask] !== -1)
return dp[i][mask];
// Generate next possible masks for the current column
let nextMask = [];
generateNextMask(n, mask, 0, 0, nextMask);
// Initialize the answer for the current state
let ans = 0;
// Iterate over all possible next masks and recursively compute the answer
for (let x of nextMask) {
ans = (ans % MOD + countWays(n, m, i + 1, x, dp) % MOD) % MOD;
}
// Memoize the result and return it
dp[i][mask] = ans;
return dp[i][mask];
}
// Driver Code
function main() {
const n = 2, m = 2;
// Initialize dp array with -1
let dp = new Array(m).fill(null).map(() => new Array(1 << n).fill(-1));
// Compute and print the number of ways to fill the grid
console.log(countWays(n, m, 0, 0, dp));
}
main();
Output
2
Time Complexity: O(2n * n * m)
Auxiliary Space: O(2n * n * m)
Contact Us