Color a grid such that all same color cells are connected either horizontally or vertically

0 0 6 minutes read

Given three integers R, C, N, and an array arr[] of size N. The task is to color all cells of a grid of R rows and C columns such that all same color cells are connected either horizontally or vertically. N represents the colors numbered from 1 to N and arr[] denotes the quantity of each color. The total quantity of color is exactly equal to the total number of cells of the grid.
Approach:

Input: R = 3, C = 5, N = 5, arr[] = {1, 2, 3, 4, 5}
Output:
1 4 4 4 3
2 5 4 5 3
2 5 5 5 3
Explanation: Available colors are 1(count = 1), 2(count = 2), 3(count = 3) etc.
For color 5: we can reach all color 5s by going horizontally or vertically through the same color 5.
Similarly for color 3, the rightmost row contains all 3 etc.
Similarly, for the rest of the colors 1, 2, 4.
Below is an invalid grid:
1 4 3 4 4
2 5 4 5 3
2 5 5 5 3
This is because the connection for the colors 3 and 4 has been broken by the invalid position of 3
in the position(0, 2).We can no longer traverse through all the 4s or all the 3s, horizontally or vertically, by passing through the respective 3s and 4s only.
Input: R = 2, C = 2, N = 3, arr[] = {2, 1, 1}
Output:
1 1
2 3

Approach:

At first glance, it might seem that graph algorithms are required. However, we are going to follow an optimized greedy algorithm.

Create a new 2D array which will be our final grid. Let us call it dp[][].
Traverse the color array A[]
For each color, i having A[i] quantities
- If the row is an odd-numbered row, fill the dp array from left to right
- Else if it is an even row, fill it from right to left
If the quantity of color is used up, move on to the next color greedily

Below is the implementation of the above approach:

C++

// C++ Program to Color a grid
// such that all same color cells
// are connected either
// horizontally or vertically
 
#include <bits/stdc++.h>
using namespace std;
 
void solve(vector<int>& arr,
        int r, int c)
{
    // Current color
    int idx = 1;
 
    // final grid
    int dp[r];
 
    for (int i = 0; i < r; i++) {
 
        // if even row
        if (i % 2 == 0) {
 
            // traverse from left to
            // right
            for (int j = 0; j < c; j++) {
 
                // if color has been exhausted
                //, move to the next color
                if (arr[idx - 1] == 0)
                    idx++;
 
                // color the grid at
                // this position
                dp[i][j] = idx;
 
                // reduce the color count
                arr[idx - 1]--;
            }
        }
        else {
 
            // traverse from right to
            // left for odd rows
            for (int j = c - 1; j >= 0; j--) {
                if (arr[idx - 1] == 0)
                    idx++;
                dp[i][j] = idx;
                arr[idx - 1]--;
            }
        }
    }
 
    // print the grid
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}
 
// Driver code
int main()
{
    int r = 3, c = 5;
    int n = 5;
    vector<int> arr
        = { 1, 2, 3, 4, 5 };
    solve(arr, r, c);
    return 0;
}

Java

// Java program to color a grid        
// such that all same color cells        
// are connected either        
// horizontally or vertically        
import java.util.*;    
 
class GFG{        
             
static void solve(List<Integer> arr,
                int r, int c)        
{
     
    // Current color        
    int idx = 1;        
             
    // Final grid        
    int[][] dp = new int[r];        
             
    for(int i = 0; i < r; i++)
    {        
         
        // If even row        
        if (i % 2 == 0)
        {
             
            // Traverse from left to        
            // right        
            for(int j = 0; j < c; j++)
            {
                 
                // If color has been exhausted
                //, move to the next color
                if (arr.get(idx - 1) == 0)    
                    idx++;
                 
                // Color the grid at
                // this position
                dp[i][j] = idx;
                 
                // Reduce the color count
                arr.set(idx - 1,
                arr.get(idx - 1) - 1);
            }
        }
        else
        {
             
            // Traverse from right to
            // left for odd rows
            for(int j = c - 1; j >= 0; j--)
            {
                if (arr.get(idx - 1) == 0)    
                    idx++;
             
                dp[i][j] = idx;
             
                arr.set(idx - 1,
                arr.get(idx - 1) - 1);
            }        
        }        
    }        
             
    // Print the grid        
    for(int i = 0; i < r; ++i)
    {        
        for(int j = 0; j < c; ++j)
        {        
            System.out.print(dp[i][j] + " ");        
        }        
        System.out.println();        
    }        
}        
         
// Driver Code        
public static void main (String[] args)
{        
    int r = 3, c = 5;        
    int n = 5;        
    List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5);
     
    solve(arr, r, c);        
}        
}
 
// This code is contributed by offbeat

Python3

# Python3 program to color a grid
# such that all same color cells
# are connected either
# horizontally or vertically
def solve(arr, r, c):
     
    # Current color
    idx = 1
 
    # Final grid
    dp = [[0 for i in range(c)]
            for i in range(r)]
 
    for i in range(r):
 
        # If even row
        if (i % 2 == 0):
 
            # Traverse from left to
            # right
            for j in range(c):
 
                # If color has been exhausted,
                # move to the next color
                if (arr[idx - 1] == 0):
                    idx += 1
 
                # Color the grid at
                # this position
                # print(i,j)
                dp[i][j] = idx
 
                # Reduce the color count
                arr[idx - 1] -= 1
        else:
 
            # Traverse from right to
            # left for odd rows
            for j in range(c - 1, -1, -1):
                if (arr[idx - 1] == 0):
                    idx += 1
                     
                dp[i][j] = idx
                arr[idx - 1] -= 1
 
    # Print the grid
    for i in range(r):
        for j in range(c):
            print(dp[i][j], end = " ")
 
        print()
 
# Driver code
if __name__ == '__main__':
 
    r = 3
    c = 5
    n = 5
    arr = [ 1, 2, 3, 4, 5 ]
     
    solve(arr, r, c)
 
# This code is contributed by mohit kumar 29

C#

// C# program to color a grid        
// such that all same color cells        
// are connected either        
// horizontally or vertically        
using System;
using System.Collections.Generic;
 
class GFG{        
             
static void solve(List<int> arr,
                int r, int c)        
{
     
    // Current color        
    int idx = 1;        
             
    // Final grid        
    int[,] dp = new int[r, c];        
             
    for(int i = 0; i < r; i++)
    {        
         
        // If even row        
        if (i % 2 == 0)
        {
             
            // Traverse from left to        
            // right        
            for(int j = 0; j < c; j++)
            {
                 
                // If color has been exhausted,
                // move to the next color
                if (arr[idx - 1] == 0)    
                    idx++;
                 
                // Color the grid at
                // this position
                dp[i, j] = idx;
                 
                // Reduce the color count
                arr[idx - 1] = arr[idx - 1] - 1;
            }
        }
        else
        {
             
            // Traverse from right to
            // left for odd rows
            for(int j = c - 1; j >= 0; j--)
            {
                if (arr[idx - 1] == 0)    
                    idx++;
             
                dp[i, j] = idx;
                arr[idx - 1] = arr[idx - 1] - 1;
            }        
        }        
    }        
             
    // Print the grid        
    for(int i = 0; i < r; ++i)
    {        
        for(int j = 0; j < c; ++j)
        {        
            Console.Write(dp[i, j] + " ");        
        }        
        Console.Write('\n');        
    }        
}        
         
// Driver Code        
public static void Main (string[] args)
{        
    int r = 3, c = 5;        
    //int n = 5;    
     
    List<int> arr = new List<int>();
    arr.Add(1);
    arr.Add(2);
    arr.Add(3);
    arr.Add(4);
    arr.Add(5);
     
    solve(arr, r, c);        
}        
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
//  Javascript Program to Color a grid
//  such that all same color cells
//  are connected either
//  horizontally or vertically
 
function solve(arr,r,c)
{
    // Current color
    var idx = 1;
 
    // final grid
    var dp = new Array(r); 
     
    var i,j;
    for(i=0;i<r;i++)
      dp[i] = new Array(c);
    for(i = 0; i < r; i++) {
 
        // if even row
        if (i % 2 == 0) {
 
            // traverse from left to
            // right
            for(j = 0; j < c; j++) {
 
                // if color has been exhausted
                //, move to the next color
                if (arr[idx - 1] == 0)
                    idx++;
 
                // color the grid at
                // this position
                dp[i][j] = idx;
 
                // reduce the color count
                arr[idx - 1]--;
            }
        }
        else {
 
            // traverse from right to
            // left for odd rows
            for (j = c - 1; j >= 0; j--) {
                if (arr[idx - 1] == 0)
                    idx++;
                dp[i][j] = idx;
                arr[idx - 1]--;
            }
        }
    }
 
    // print the grid
    for(i = 0; i < r; ++i) {
        for(j = 0; j < c; ++j) {
            document.write(dp[i][j] + " ");
        }
        document.write("<br>");
    }
}
 
// Driver code
      
    var r = 3, c = 5;
    var n = 5;
    var arr = [1, 2, 3, 4, 5];
    solve(arr, r, c);
 
</script>

Output:

1 2 2 3 3
4 4 4 4 3
5 5 5 5 5

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!