Given a matrix arr[][] of dimensions N * M, consisting of ‘O’ or ‘F’, where ‘O’ denotes obstacles and ‘F’ denotes free spaces, the task is to replace all ‘F’s in the given matrix by either ‘1’ or ‘2’, such that no two adjacent cells have the same value.
Examples:
Input: N = 4, M = 4, arr[][] = {{‘F’, ‘F’, ‘F’, ‘F’}, {‘F’, ‘O’, ‘F’, ‘F’}, {‘F’, ‘F’, ‘O’, ‘F’}, {‘F’, ‘F’, ‘F’, ‘F’}}
Output:
1 2 1 2
2 O 2 1
1 2 O 2
2 1 2 1Input: N = 1, M = 1, arr[][] = {{‘O’}}
Output:
Naive Approach: The simplest approach to solve the problem is to use Backtracking, similar to the Sudoku problem. But, instead of placing N different values in a given position, either 1 or 2 is required to be placed on cells containing ‘F’ such that no two adjacent elements are equal to each other. Follow the steps below to solve the problem:
- Create a function to check if the given position in the matrix is valid or not.
- If the end of the matrix has been reached, i.e. i = N and j = M, then return True.
- Otherwise, if the current index is a free space, i.e arr[i][j]==’F’ , then fill the index with either ‘1’ or ‘2’. If any cell is found to be invalid, i.e. any of its adjacent cells has the same value, then print “No”.
- After complete traversal of the matrix, if all the ‘F’s were replaced such that no adjacent matrix elements are same, then print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if current// position is safe or notbool issafe(vector<vector<char> >& v, int i, int j, int n, int m, char ch){ // Directions for adjacent cells int rowN[] = { 1, -1, 0, 0 }; int colN[] = { 0, 0, 1, -1 }; for (int k = 0; k < 4; k++) { // Check if any adjacent cell is same if (i + rowN[k] >= 0 && i + rowN[k] < n && j + colN[k] >= 0 && j + colN[k] < m && v[i + rowN[k]][j + colN[k]] == ch) { return false; } } // Current index is valid return true;}// Recursive function for backtrackingbool place(vector<vector<char> >& v, int n, int m){ int i, j; for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { // Free cell if (v[i][j] == 'F') { break; } } if (j != m) { break; } } // All positions covered if (i == n && j == m) { return true; } // If position is valid for 1 if (issafe(v, i, j, n, m, '1')) { v[i][j] = '1'; if (place(v, n, m)) { return true; } v[i][j] = 'F'; } // If position is valid for 2 if (issafe(v, i, j, n, m, '2')) { v[i][j] = '2'; // Recursive call for next // unoccupied position if (place(v, n, m)) { return true; } // If above conditions fails v[i][j] = 'F'; } return false;}// Function to print valid matrixvoid printMatrix(vector<vector<char> > arr, int n, int m){ place(arr, n, m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << arr[i][j]; } cout << endl; }}// Driver Codeint main(){ // Given matrix vector<vector<char> > arr = { { 'F', 'F', 'F', 'F' }, { 'F', 'O', 'F', 'F' }, { 'F', 'F', 'O', 'F' }, { 'F', 'F', 'F', 'F' }, }; // Give dimensions int n = 4, m = 4; // Function call printMatrix(arr, n, m); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { public static boolean issafe(char v[][], int i, int j, int n, int m, char ch) { // Directions for adjacent cells int rowN[] = { 1, -1, 0, 0 }; int colN[] = { 0, 0, 1, -1 }; for (int k = 0; k < 4; k++) { // Check if any adjacent cell is same if (i + rowN[k] >= 0 && i + rowN[k] < n && j + colN[k] >= 0 && j + colN[k] < m && v[i + rowN[k]][j + colN[k]] == ch) { return false; } } // Current index is valid return true; } // Recursive function for backtracking public static boolean place(char v[][], int n, int m) { int i=0, j=0; for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { // Free cell if (v[i][j] == 'F') { break; } } if (j != m) { break; } } // All positions covered if (i == n && j == m) { return true; } // If position is valid for 1 if (issafe(v, i, j, n, m, '1')) { v[i][j] = '1'; if (place(v, n, m)) { return true; } v[i][j] = 'F'; } // If position is valid for 2 if (issafe(v, i, j, n, m, '2')) { v[i][j] = '2'; // Recursive call for next // unoccupied position if (place(v, n, m)) { return true; } // If above conditions fails v[i][j] = 'F'; } return false; } // Function to print valid matrix public static void printMatrix(char arr[][], int n, int m) { place(arr, n, m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { System.out.print(arr[i][j]); } System.out.println(); } } // Driver Code public static void main (String[] args) { char arr[][] = { { 'F', 'F', 'F', 'F' }, { 'F', 'O', 'F', 'F' }, { 'F', 'F', 'O', 'F' }, { 'F', 'F', 'F', 'F' }, }; // Give dimensions int n = 4, m = 4; // Function call printMatrix(arr, n, m); }} |
Python3
# Python program for the above approachdef issafe(v, i, j, n, m, ch): # Directions for adjacent cells rowN = [1, -1, 0, 0] colN = [0, 0, 1, -1] for k in range(4): # Check if any adjacent cell is same if (i + rowN[k] >= 0 and i + rowN[k] < n and j + colN[k] >= 0 and j + colN[k] < m and v[i + rowN[k]][j + colN[k]] == ch): return False # Current index is valid return True# Recursive function for backtrackingdef place(v, n, m): for i in range(n): for j in range(m): # Free cell if (v[i][j] == 'F'): # If position is valid for 1 if issafe(v, i, j, n, m, '1'): v[i][j] = '1' # If all positions are covered if place(v, n, m): return True v[i][j] = 'F' # If position is valid for 2 if issafe(v, i, j, n, m, '2'): v[i][j] = '2' # If all positions are covered if place(v, n, m): return True v[i][j] = 'F' # No valid position found return False # All positions covered return True# Function to print valid matrixdef printMatrix(arr, n, m): place(arr, n, m) for i in range(n): for j in range(m): print(arr[i][j], end="") print()# Driver Codearr = [['F', 'F', 'F', 'F'], ['F', 'O', 'F', 'F'], ['F', 'F', 'O', 'F'], ['F', 'F', 'F', 'F']]# Give dimensionsn, m = 4, 4# Function callprintMatrix(arr, n, m) |
C#
// C# program for the above approach using System;class GFG{// Function to check if current// position is safe or not public static bool issafe(char[,] v, int i, int j, int n, int m, char ch){ // Directions for adjacent cells int[] rowN = { 1, -1, 0, 0 }; int[] colN = { 0, 0, 1, -1 }; for(int k = 0; k < 4; k++) { // Check if any adjacent cell is same if (i + rowN[k] >= 0 && i + rowN[k] < n && j + colN[k] >= 0 && j + colN[k] < m && v[(i + rowN[k]), (j + colN[k])] == ch) { return false; } } // Current index is valid return true;}// Recursive function for backtrackingpublic static bool place(char[,] v, int n, int m){ int i = 0, j = 0; for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Free cell if (v[i, j] == 'F') { break; } } if (j != m) { break; } } // All positions covered if (i == n && j == m) { return true; } // If position is valid for 1 if (issafe(v, i, j, n, m, '1')) { v[i, j] = '1'; if (place(v, n, m)) { return true; } v[i, j] = 'F'; } // If position is valid for 2 if (issafe(v, i, j, n, m, '2')) { v[i, j] = '2'; // Recursive call for next // unoccupied position if (place(v, n, m)) { return true; } // If above conditions fails v[i, j] = 'F'; } return false;}// Function to print valid matrixpublic static void printMatrix(char[,] arr, int n, int m){ place(arr, n, m); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { Console.Write(arr[i, j]); } Console.WriteLine(); }}// Driver Codepublic static void Main() { char[,] arr = { { 'F', 'F', 'F', 'F' }, { 'F', 'O', 'F', 'F' }, { 'F', 'F', 'O', 'F' }, { 'F', 'F', 'F', 'F' },}; // Give dimensions int n = 4, m = 4; // Function call printMatrix(arr, n, m);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// JavaScript program to implement// the above approachfunction issafe(v, i, j, n, m, ch) { // Directions for adjacent cells let rowN = [ 1, -1, 0, 0 ]; let colN = [ 0, 0, 1, -1 ]; for (let k = 0; k < 4; k++) { // Check if any adjacent cell is same if (i + rowN[k] >= 0 && i + rowN[k] < n && j + colN[k] >= 0 && j + colN[k] < m && v[i + rowN[k]][j + colN[k]] == ch) { return false; } } // Current index is valid return true; } // Recursive function for backtracking function place(v, n, m) { let i=0, j=0; for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { // Free cell if (v[i][j] == 'F') { break; } } if (j != m) { break; } } // All positions covered if (i == n && j == m) { return true; } // If position is valid for 1 if (issafe(v, i, j, n, m, '1')) { v[i][j] = '1'; if (place(v, n, m)) { return true; } v[i][j] = 'F'; } // If position is valid for 2 if (issafe(v, i, j, n, m, '2')) { v[i][j] = '2'; // Recursive call for next // unoccupied position if (place(v, n, m)) { return true; } // If above conditions fails v[i][j] = 'F'; } return false; } // Function to print valid matrix function printMatrix(arr, n, m) { place(arr, n, m); for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { document.write(arr[i][j]); } document.write("<br/>"); } }// Driver code let arr = [ [ 'F', 'F', 'F', 'F' ], [ 'F', 'O', 'F', 'F' ], [ 'F', 'F', 'O', 'F' ], [ 'F', 'F', 'F', 'F' ], ]; // Give dimensions let n = 4, m = 4; // Function call printMatrix(arr, n, m); </script> |
Output
1212 2O21 12O2 2121
Time Complexity: O(2N*M)
Auxiliary Space: O(N*M)
Efficient Approach: The idea is to simply replace any ‘F’ by 1 if the parity of cell (i, j) is 1 i.e., (i + j) % 2 is 1. Otherwise, replace that ‘F’ by 2. Follow the steps below to solve the problem:
- Traverse the given matrix.
- For each cell (i, j) traversed, if cell arr[i][j] is equal to ‘F’ and (i + j) % 2 is equal to 1, assign arr[i][j] = 1. Otherwise, assign arr[i][j] = 2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to display the valid matrixvoid print(vector<vector<char> > arr, int n, int m){ // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char a = arr[i][j]; // If the current cell is a free // space and is even-indexed if ((i + j) % 2 == 0 && a == 'F') { arr[i][j] = '1'; } // If the current cell is a free // space and is odd-indexed else if (a == 'F') { arr[i][j] = '2'; } } } // Print the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << arr[i][j]; } cout << endl; }}// Driver Codeint main(){ // Given N and M int n = 4, m = 4; // Given matrix vector<vector<char> > arr = { { 'F', 'F', 'F', 'F' }, { 'F', 'O', 'F', 'F' }, { 'F', 'F', 'O', 'F' }, { 'F', 'F', 'F', 'F' }, }; // Function call print(arr, n, m); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to display the valid matrix public static void print(char arr[][], int n, int m) { // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char a = arr[i][j]; // If the current cell is a free // space and is even-indexed if ((i + j) % 2 == 0 && a == 'F') { arr[i][j] = '1'; } // If the current cell is a free // space and is odd-indexed else if (a == 'F') { arr[i][j] = '2'; } } } // Print the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { System.out.print(arr[i][j]); } System.out.println(); } } // Driver Code public static void main (String[] args) { // Given N and M int n = 4, m = 4; // Given matrix char arr[][] = { { 'F', 'F', 'F', 'F' }, { 'F', 'O', 'F', 'F' }, { 'F', 'F', 'O', 'F' }, { 'F', 'F', 'F', 'F' }}; // Function call print(arr, n, m); }} |
Python3
# Python3 program for the above approach# Function to display the valid matrixdef Print(arr, n, m): # Traverse the matrix for i in range(n): for j in range(m): a = arr[i][j] # If the current cell is a free # space and is even-indexed if ((i + j) % 2 == 0 and a == 'F') : arr[i][j] = '1' # If the current cell is a free # space and is odd-indexed elif (a == 'F') : arr[i][j] = '2' # Print the matrix for i in range(n) : for j in range(m) : print(arr[i][j], end = "") print()# Given N and Mn, m = 4, 4# Given matrixarr = [ [ 'F', 'F', 'F', 'F' ], [ 'F', 'O', 'F', 'F' ], [ 'F', 'F', 'O', 'F' ], [ 'F', 'F', 'F', 'F' ]]# Function callPrint(arr, n, m)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;class GFG{ // Function to display the valid matrixpublic static void print(char[,] arr, int n, int m){ // Traverse the matrix for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { char a = arr[i, j]; // If the current cell is a free // space and is even-indexed if ((i + j) % 2 == 0 && a == 'F') { arr[i, j] = '1'; } // If the current cell is a free // space and is odd-indexed else if (a == 'F') { arr[i, j] = '2'; } } } // Print the matrix for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { Console.Write(arr[i, j]); } Console.WriteLine(); }}// Driver Codepublic static void Main() { // Given N and M int n = 4, m = 4; // Given matrix char[,] arr = { { 'F', 'F', 'F', 'F' }, { 'F', 'O', 'F', 'F' }, { 'F', 'F', 'O', 'F' }, { 'F', 'F', 'F', 'F' }}; // Function call print(arr, n, m);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Java Script program for the above approach // Function to display the valid matrix function print(arr,n,m) { // Traverse the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { let a = arr[i][j]; // If the current cell is a free // space and is even-indexed if ((i + j) % 2 == 0 && a == 'F') { arr[i][j] = '1'; } // If the current cell is a free // space and is odd-indexed else if (a == 'F') { arr[i][j] = '2'; } } } // Print the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { document.write(arr[i][j]); } document.write("<br>"); } } // Driver Code // Given N and M let n = 4, m = 4; // Given matrix let arr = [ ['F', 'F', 'F', 'F' ], [ 'F', 'O', 'F', 'F' ], [ 'F', 'F', 'O', 'F' ], [ 'F', 'F', 'F', 'F' ]]; // Function call print(arr, n, m); // This code is contributed by sravan.</script> |
Output
1212 2O21 12O2 2121
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
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!
