Given a matrix arr[][] of dimensions N * M where each cell consists of characters ‘R’ or ‘D’ except the cell arr[N][M] which contains ‘F’. ‘R’ and ‘D’ denotes that the player can move in the right and down direction respectively from the current cell. The task is to find the minimum number of characters required to be flipped from ‘R’ to ‘D’ or ‘D’ to ‘R’ such that it is possible to reach the finishing cell i.e., arr[N][M] from every cell.
Examples:
Input: N = 2, M = 3, arr[][] = {{D, D, R}, {R, R, F}}
Output: 1
Explanation: After changing the direction of (1, 3) to ‘D’, each cell can reach the finishing point.Input: N = 1, M = 3, arr[1][3] = {{D, D, F}}
Output: 2
Approach: The problem can be solved by observing that each cell can reach the finishing point after changing the following cells:
- Change all the ‘D’s to ‘R’ in the last row.
- Change all the ‘R’ to ‘D’ in the last column.
Follow the steps below to solve the problem:
- Initialize a variable, say ans, to store the minimum number of flips.
- Traverse from i = 0 to N – 1 and count the number of cells arr[i][M-1] which contains ‘R’.
- Traverse from i = 0 to M – 1 and count the number of cells arr[N – 1][i] which contains ‘D’.
- Print the sum of the two counts obtained in the above step as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum// number of flips requiredint countChanges(vector<vector<char> > mat){ // Dimensions of mat[][] int n = mat.size(); int m = mat[0].size(); // Initialize answer int ans = 0; // Count all 'D's in the last row for (int j = 0; j < m - 1; j++) { if (mat[n - 1][j] != 'R') ans++; } // Count all 'R's in the last column for (int i = 0; i < n - 1; i++) { if (mat[i][m - 1] != 'D') ans++; } // Print answer return ans;}// Driver Codeint main(){ // Given matrix vector<vector<char> > arr = { { 'R', 'R', 'R', 'D' }, { 'D', 'D', 'D', 'R' }, { 'R', 'D', 'R', 'F' } }; // Function call int cnt = countChanges(arr); // Print answer cout << cnt << endl; return 0;} |
Java
// Java program for the above approach import java.io.*;class GFG{ // Function to calculate the minimum // number of flips required public static int countChanges(char mat[][]){ // Dimensions of mat[][] int n = mat.length; int m = mat[0].length; // Initialize answer int ans = 0; // Count all 'D's in the last row for(int j = 0; j < m - 1; j++) { if (mat[n - 1][j] != 'R') ans++; } // Count all 'R's in the last column for(int i = 0; i < n - 1; i++) { if (mat[i][m - 1] != 'D') ans++; } // Print answer return ans;}// Driver Code public static void main(String[] args){ char arr[][] = { { 'R', 'R', 'R', 'D' }, { 'D', 'D', 'D', 'R' }, { 'R', 'D', 'R', 'F' } }; // Function call int cnt = countChanges(arr); // Print answer System.out.println(cnt);}}// This code is contributed by Manu Pathria |
Python3
# Python3 program for the above approach # Function to calculate the minimum# number of flips requireddef countChanges(mat): # Dimensions of mat[][] n = len(mat) m = len(mat[0]) # Initialize answer ans = 0 # Count all 'D's in the last row for j in range(m - 1): if (mat[n - 1][j] != 'R'): ans += 1 # Count all 'R's in the last column for i in range(n - 1): if (mat[i][m - 1] != 'D'): ans += 1 # Print answer return ans# Driver Code# Given matrixarr = [ [ 'R', 'R', 'R', 'D' ] , [ 'D', 'D', 'D', 'R' ], [ 'R', 'D', 'R', 'F' ] ] # Function callcnt = countChanges(arr) # Print answer print(cnt)# This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approach using System;class GFG{ // Function to calculate the minimum // number of flips required public static int countChanges(char [,]mat){ // Dimensions of [,]mat int n = mat.GetLength(0); int m = mat.GetLength(1); // Initialize answer int ans = 0; // Count all 'D's in the last row for(int j = 0; j < m - 1; j++) { if (mat[n - 1,j] != 'R') ans++; } // Count all 'R's in the last column for(int i = 0; i < n - 1; i++) { if (mat[i,m - 1] != 'D') ans++; } // Print answer return ans;}// Driver Code public static void Main(String[] args){ char [,]arr = { { 'R', 'R', 'R', 'D' }, { 'D', 'D', 'D', 'R' }, { 'R', 'D', 'R', 'F' } }; // Function call int cnt = countChanges(arr); // Print answer Console.WriteLine(cnt);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to calculate the minimum// number of flips required function countChanges(mat){ // Dimensions of mat[][] let n = mat.length; let m = mat[0].length; // Initialize answer let ans = 0; // Count all 'D's in the last row for(let j = 0; j < m - 1; j++) { if (mat[n - 1][j] != 'R') ans++; } // Count all 'R's in the last column for(let i = 0; i < n - 1; i++) { if (mat[i][m - 1] != 'D') ans++; } // Print let answer return ans;}// Driver codelet arr = [ [ 'R', 'R', 'R', 'D' ], [ 'D', 'D', 'D', 'R' ], [ 'R', 'D', 'R', 'F' ] ];// Function calllet cnt = countChanges(arr);// Print let answerdocument.write(cnt);// This code is contributed by code_hunt </script> |
Output:
2
Time Complexity: O(N+M), where N and M are matrix dimensions.
Auxiliary Space: O(1) , since there is no extra space involved.
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!
