Given a 2D array grid[][] of size N * M, consisting of the characters “1”, “0”, and “*”, where “*” denotes an empty space and can be replaced by either a “1” or a “0”. The task is to fill the grid such that “0” and “1” occur alternatively and no two consecutive characters occur together, i.e. (101010) is valid and (101101) is not because two “1” occurs simultaneously. If it is possible to do so, print Yes and the possible 2-D array. Otherwise, print No.

Examples:

Input: N = 4, M = 4 grid[][] = { {**10}, {****}, {****}, {**01}}
Output: Yes
1010
0101
1010
0101
Explanation: Create a grid with alternating “1” and “0” characters so the answer is Yes, followed by the filled characters.

Input: N = 4, M = 4, grid[][] = {{*1*0}, {****}, {**10}, {****}}
Output: No
Explanation: In the first row, 1 and 0 have one cell blank which can neither be filled with 1 nor 0.

Approach: There are only 2 possibilities for a possible 2-D array one, with starting 1 and one with starting 0. Generate both of them and check if any one of them matches with the given 2-D array grid[][]. Follow the steps below to solve the problem:

• Define a function createGrid(char grid[][1001], bool is1, int N, int M) and perform the following tasks:
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • Iterate over the range [0, M] using the variable j and performing the following tasks:
      • If is1 is true, then set grid[i][j] to ‘0’ and set is1 to false.
      • Else, then set grid[i][j] to ‘1’ and set is1 to true.
    • If M%2 is equal to 0, then set the value of is1 to not of is1.
• Define a function testGrid(char testGrid[][1001], char Grid[][1001], int N, int M) and perform the following tasks:
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • Iterate over the range [0, M] using the variable j and performing the following tasks:
      • If Grid[i][j] is not equal to ‘*’ and testGrid[i][j] is not equal to Grid[i][j], then return false.
  • After performing the above steps, return the value of true as the answer.
• Define a function printGrid(char grid[][1001], int N, int M) and perform the following tasks:
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • Iterate over the range [0, M] using the variable j and performing the following tasks:
      • Print the value of grid[i][j].
• Initialize two 2-D arrays gridTest1[N][1001] and gridTest2[N][1001] to store the possible alternating grids.
• Call the function createGrid(gridTest1, true, N, M) and createGrid(gridTest2, false, N, M) to form the possible alternating grids.
• If the function testGrid(gridTest1, grid, N, M) returns true, then call the function printGrid(gridTest1, N, M) to print the grid as the answer.
• Else If, the function testGrid(gridTest2, grid, N, M) returns true, then call the function printGrid(gridTest2, N, M) to print the grid as the answer.
• Else, print No as the answer.

Below is the implementation of the above approach.

Yes
1 0 1 0 
0 1 0 1 
1 0 1 0 
0 1 0 1 

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)

Efficient Approach: The idea is to use two variables instead of creating the 2-D arrays to maintain the possible alternating arrays. Follow the steps below to solve the problem:

• Define a function posCheck(char grid[][1001], int N, int M, char check) and perform the following tasks:
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • Iterate over the range [0, M] using the variable j and performing the following tasks:
      • If grid[i][j] is equal to ‘*’, then continue.
      • Else, if (i+j)%2 is equal to 1 and grid[i][j] is not equal to check, then return false.
      • Else, if (i+j)%2 is equal to 0 and grid[i][j] is equal to check, then return false.
  • After performing the above steps, return the value of true as the answer.
• Define a function posCheck(char grid[][1001], int N, int M, char odd, char even) and perform the following tasks:
  • Iterate over the range [0, N] using the variable i and performing the following tasks:
    • Iterate over the range [0, M] using the variable j and performing the following tasks:
      • If (i+j)%2 is equal to 1, then set the value of grid[i][j] to odd else even.
• Initialize the bool variable flag as true.
• Initialize the variables k and o as -1 to store the value of the first cell which doesn’t have the character ‘*’.
• Iterate over the range [0, N] using the variable i and performing the following tasks:
  • Iterate over the range [0, M] using the variable j and performing the following tasks:
    • If Grid[i][j] is not equal to ‘*’, then set the value of k as i and o as j and break.
  • If k is not equal to -1, then break.
• If k is not equal to -1, then call the function PosCheck(grid, n, m, ‘1’) and store the value returned by the function in the variable flag and if flag is true, then call the function fill(grid, n, m, ‘1’, ‘0’) to fill the grid in one of the possible ways.
• If flag is false, then call the function PosCheck(grid, n, m, ‘0’) and store the value returned by the function in the variable flag and if flag is true, then call the function fill(grid, n, m, ‘0’, ‘1’) to fill the grid in one of the possible ways.
• If k is equal to -1, then, initialize the char variable h as ‘0’.
• Iterate over the range [0, M] using the variable i and performing the following tasks:
  • Set the value of grid[0][i] as h and if h is ‘0‘, then set it to ‘1‘, otherwise ‘0’.
• Iterate over the range [0, N] using the variable i and performing the following tasks:
  • Iterate over the range [0, M] using the variable j and performing the following tasks:
    • If i-1 is less than 0, then continue.
    • If grid[i-1][j] is ‘1’, then set it to ‘0’, else ‘1’.
• Set the value of flag as true as the grid is made alternating.
• If flag is false, then print “NO”.
• Else, print “YES” and print the elements of the grid[][].

Below is the implementation of the above approach. 

YES
1010
0101
1010
0101

Time Complexity: O(N*M)
Auxiliary Space: O(1)