Replace specified matrix elements such that no two adjacent elements are equal | C ++ program for the above approach ; Function to check if current position is safe or not ; Directions for adjacent cells ; Check if any adjacent cell is same ; Current index is valid ; Recursive function for backtracking ; Free cell ; All positions covered ; If position is valid for 1 ; If position is valid for 2 ; Recursive call for next unoccupied position ; If above conditions fails ; Function to print valid matrix ; Driver Code ; Give dimensions ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool issafe ( vector < vector < char > > & v , int i , int j , int n , int m , char ch ) { int rowN [ ] = { 1 , -1 , 0 , 0 } ; int colN [ ] = { 0 , 0 , 1 , -1 } ; for ( int k = 0 ; k < 4 ; k ++ ) { 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 ; } } return true ; } bool place ( vector < vector < char > > & v , int n , int m ) { int i , j ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < m ; j ++ ) { if ( v [ i ] [ j ] == ' F ' ) { break ; } } if ( j != m ) { break ; } } if ( i == n && j == m ) { return true ; } if ( issafe ( v , i , j , n , m , '1' ) ) { v [ i ] [ j ] = '1' ; if ( place ( v , n , m ) ) { return true ; } v [ i ] [ j ] = ' F ' ; } if ( issafe ( v , i , j , n , m , '2' ) ) { v [ i ] [ j ] = '2' ; if ( place ( v , n , m ) ) { return true ; } v [ i ] [ j ] = ' F ' ; } return false ; } void 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 ; } } int main ( ) { vector < vector < char > > arr = { { ' F ' , ' F ' , ' F ' , ' F ' } , { ' F ' , ' O ' , ' F ' , ' F ' } , { ' F ' , ' F ' , ' O ' , ' F ' } , { ' F ' , ' F ' , ' F ' , ' F ' } , } ; int n = 4 , m = 4 ; printMatrix ( arr , n , m ) ; return 0 ; }