Given a 2D array arr[][] of size N*M consisting of ‘.’ and ‘*’ characters representing a floor and two positive integers A and B representing the cost of a 1*1 and 1*2 tile respectively, the task is to fill all the characters having ‘.’ on the floor with the tiles of dimensions 1*1 or 1*2 such that the cost of filling the floor is minimized and rotation of the tiles is not allowed.
Examples:
Input: A = 2, B = 10, arr[][] = {{‘.’, ‘.’, ‘*’}, {‘.’, ‘*’, ‘*’}}
Output: 6
Explanation:
Cover arr[0][0] with 1*1 tile, arr[0][1] with 1*1 tile and arr[1][0] with 1*1 tile.
Therefore, the minimum cost is 2 + 2 +2 = 6.Input: A = 2, B = 6, arr[][] = {{‘.’, ‘.’, ‘.’}, {‘*’, ‘*’, ‘.’}, {‘.’, ‘.’, ‘*’}}
Output: 12
Approach: The given problem can be solved by using the Greedy Approach. The idea is to traverse the given 2D array row-wise, and if two consecutive ‘.’ is encountered, then choose the tile with a minimum cost of placing two 1 * 1 tiles or one 1 * 2 tile. Follow the steps below to solve the problem:
- Initialize a variable, say ans as 0 to store the minimum total cost.
- Traverse the given 2D array arr[][] row-wise using i for row-index and j for column index and perform the following steps:
- If the value of arr[i][j] is equal to ‘*’, then continue the iteration.
- Otherwise, check for the following conditions:
- If the value of j is m(M – 1), then add A to the variable ans.
- Otherwise, if the value of (arr[i][j + 1]) is ‘.’, then add the minimum of the values 2*A and B to the variable ans.
- In all other cases, add the value of A to the variable ans.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost// of flooring with the given tilesvoid minCost(vector<vector<char> > arr, int A, int B){ // Store the size of the 2d array int n = arr.size(); int m = arr[0].size(); // Stores the minimum cost of // flooring int ans = 0; // Traverse the 2d array row-wise for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the current character // is '*', then skip it if (arr[i][j] == '*') continue; // Choose the 1*1 tile if // j is m-1 if (j == m - 1) ans += A; // If consecutive '.' are // present, the greedily // choose tile with the // minimum cost else { if (arr[i][j + 1] == '.') { ans += min(2 * A, B); j++; } // Otherwise choose // the 1*1 tile else ans += A; } } } // Print the minimum cost cout << ans;}// Driver Codeint main(){ vector<vector<char> > arr = { { '.', '.', '*' }, { '.', '*', '*' } }; int A = 2, B = 10; minCost(arr, A, B); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class MyClass{ // Function to find the minimum cost// of flooring with the given tilesstatic void minCost(char arr[][], int A, int B){ // Store the size of the 2d array int n = arr.length; int m = arr[0].length; // Stores the minimum cost of // flooring int ans = 0; // Traverse the 2d array row-wise for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the current character // is '*', then skip it if (arr[i][j] == '*') continue; // Choose the 1*1 tile if // j is m-1 if (j == m - 1) ans += A; // If consecutive '.' are // present, the greedily // choose tile with the // minimum cost else { if (arr[i][j + 1] == '.') { ans += Math.min(2 * A, B); j++; } // Otherwise choose // the 1*1 tile else ans += A; } } } // Print the minimum cost System.out.println(ans);}// Driver Codepublic static void main(String args[]){ char [][]arr = { { '.', '.', '*' }, { '.', '*', '*' } }; int A = 2, B = 10; minCost(arr, A, B);}}// This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach# Function to find the minimum cost# of flooring with the given tilesdef minCost(arr, A, B): # Store the size of the 2d array n = len(arr) m = len(arr[0]) # Stores the minimum cost of # flooring ans = 0 # Traverse the 2d array row-wise for i in range(n): j = 0 while j < m: # If the current character # is '*', then skip it if (arr[i][j] == '*'): j += 1 continue # Choose the 1*1 tile if # j is m-1 if (j == m - 1): ans += A # If consecutive '.' are # present, the greedily # choose tile with the # minimum cost else: if (arr[i][j + 1] == '.'): ans += min(2 * A, B) j += 1 # Otherwise choose # the 1*1 tile else: ans += A j += 1 # Print the minimum cost print (ans)# Driver Codeif __name__ == '__main__': arr = [ [ '.', '.', '*' ], [ '.', '*', '*' ] ] A, B = 2, 10 minCost(arr, A, B)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the minimum cost// of flooring with the given tilesstatic void minCost(char[,] arr, int A, int B){ // Store the size of the 2d array int n = arr.GetLength(0); int m = arr.GetLength(1); // Stores the minimum cost of // flooring int ans = 0; // Traverse the 2d array row-wise for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the current character // is '*', then skip it if (arr[i,j] == '*') continue; // Choose the 1*1 tile if // j is m-1 if (j == m - 1) ans += A; // If consecutive '.' are // present, the greedily // choose tile with the // minimum cost else { if (arr[i,j + 1] == '.') { ans += Math.Min(2 * A, B); j++; } // Otherwise choose // the 1*1 tile else ans += A; } } } // Print the minimum cost Console.WriteLine(ans);} // Driver Code static public void Main () { char[,] arr = { { '.', '.', '*' }, { '.', '*', '*' } }; int A = 2, B = 10; minCost(arr, A, B); }}// This code is contributed by patel2127. |
Javascript
<script>// JavaScript program for the above approach // Function to find the minimum cost // of flooring with the given tiles function minCost(arr, A, B) { // Store the size of the 2d array let n = arr.length; let m = arr[0].length; // Stores the minimum cost of // flooring let ans = 0; // Traverse the 2d array row-wise for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { // If the current character // is '*', then skip it if (arr[i][j] == '*') continue; // Choose the 1*1 tile if // j is m-1 if (j == m - 1) ans += A; // If consecutive '.' are // present, the greedily // choose tile with the // minimum cost else { if (arr[i][j + 1] == '.') { ans += Math.min(2 * A, B); j++; } // Otherwise choose // the 1*1 tile else ans += A; } } } //Print the minimum cost document.write(ans); } // Driver Code var arr = [['.', '.', '*'], ['.', '*', '*']]; let A = 2, B = 10; minCost(arr, A, B); // This code is contributed by Potta Lokesh </script> |
Output:
6
Time Complexity: O(N * M)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
