Replace specified matrix elements such that no two adjacent elements are equal | Java 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
import java . io . * ; class GFG { public static boolean issafe ( 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 ; } 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 ++ ) { 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 ; } 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 ( ) ; } } public static void main ( String [ ] args ) { 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 ) ; } }