Comprobar si los elementos de una Array Binaria se pueden hacer alternando

Posted on by Rudeus Greyrat

Dada una cuadrícula de array 2D [][] de tamaño N * M , que consta de los caracteres «1», «0» y «*» , donde «*» denota un espacio vacío y puede ser reemplazado por un «1» o un “0” . La tarea es llenar la cuadrícula de modo que «0» y «1» ocurran alternativamente y no ocurran dos caracteres consecutivos juntos, es decir, (101010) es válido y (101101) no lo es porque dos «1» ocurren simultáneamente. Si es posible, imprima Sí y la array 2-D posible . De lo contrario , imprima No.

Ejemplos:

Entrada: N = 4, M = 4 grid[][] = { {**10}, {****}, {****}, {**01}}
Salida: Sí
1010
0101
1010
0101
Explicación : Cree una cuadrícula alternando los caracteres «1» y «0» para que la respuesta sea Sí, seguida de los caracteres rellenos.

Entrada: N = 4, M = 4, grid[][] = {{*1*0}, {****}, {**10}, {****}}
Salida: No
Explicación: In la primera fila, 1 y 0 tienen una celda en blanco que no se puede llenar con 1 ni con 0.

Enfoque: solo hay 2 posibilidades para una posible array 2-D , con inicio 1 y otra con inicio 0. Genere ambos y verifique si alguno de ellos coincide con la cuadrícula de array 2-D dada [] []. Siga los pasos a continuación para resolver el problema:

  • Defina una función createGrid(char grid[][1001], bool is1, int N, int M) y realice las siguientes tareas:
    • Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
      • Itere sobre el rango [0, M] usando la variable j y realizando las siguientes tareas:
        • Si is1 es verdadero, establezca grid[i][j] en ‘0’ y establezca is1 en falso.
        • De lo contrario, establezca grid[i][j] en ‘1’ y establezca is1 en verdadero.
      • Si M%2 es igual a 0, establezca el valor de is1 en not of is1.
  • Defina una función testGrid(char testGrid[][1001], char Grid[][1001], int N, int M) y realice las siguientes tareas:
    • Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
      • Itere sobre el rango [0, M] usando la variable j y realizando las siguientes tareas:
        • Si Grid[i][j] no es igual a ‘*’ y testGrid[i][j] no es igual a Grid[i][j], entonces devuelve false.
    • Después de realizar los pasos anteriores, devuelve el valor de verdadero como respuesta.
  • Defina una función printGrid(char grid[][1001], int N, int M) y realice las siguientes tareas:
  • Inicialice dos arrays 2-D gridTest1[N][1001] y gridTest2[N][1001] para almacenar las posibles cuadrículas alternas.
  • Llame a la función createGrid(gridTest1, true, N, M) y createGrid(gridTest2, false, N, M) para formar las posibles cuadrículas alternas.
  • Si la función testGrid(gridTest1, grid, N, M) devuelve verdadero, llame a la función printGrid(gridTest1, N, M) para imprimir la cuadrícula como respuesta.
  • De lo contrario, si la función testGrid(gridTest2, grid, N, M) devuelve verdadero, llame a la función printGrid(gridTest2, N, M) para imprimir la cuadrícula como respuesta.
  • De lo contrario, escriba No como respuesta.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to create the possible grids
void createGrid(char grid[][1001], bool is1,
                int N, int M)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
 
            if (is1) {
                grid[i][j] = '0';
                is1 = false;
            }
            else {
                grid[i][j] = '1';
                is1 = true;
            }
        }
        if (M % 2 == 0)
            is1 = !is1;
    }
}
 
// Function to test if any one of them
// matches with the given 2-D array
bool testGrid(char testGrid[][1001],
              char Grid[][1001],
              int N, int M)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
 
            if (Grid[i][j] != '*') {
 
                if (Grid[i][j] != testGrid[i][j]) {
                    return false;
                }
            }
        }
    }
    return true;
}
 
// Function to print the grid, if possible
void printGrid(char grid[][1001], int N, int M)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}
 
// Function to check if the grid
// can be made alternating or not
void findPossibleGrid(int N, int M,
                      char grid[][1001])
{
    // Grids to store the possible grids
    char gridTest1[N][1001], gridTest2[N][1001];
 
    createGrid(gridTest1, true, N, M);
 
    createGrid(gridTest2, false, N, M);
 
    if (testGrid(gridTest1, grid, N, M)) {
 
        cout << "Yes\n";
        printGrid(gridTest1, N, M);
    }
    else if (testGrid(gridTest2, grid, N, M)) {
 
        cout << "Yes\n";
        printGrid(gridTest2, N, M);
    }
    else {
        cout << "No\n";
    }
}
 
// Driver Code
int main()
{
    int N = 4, M = 4;
    char grid[][1001] = { { '*', '*', '1', '0' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '0', '1' } };
 
    findPossibleGrid(N, M, grid);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to create the possible grids
public static void createGrid(char[][] grid,
                              boolean is1,
                              int N, int M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if (is1)
            {
                grid[i][j] = '0';
                is1 = false;
            }
            else
            {
                grid[i][j] = '1';
                is1 = true;
            }
        }
        if (M % 2 == 0)
            is1 = !is1;
    }
}
 
// Function to test if any one of them
// matches with the given 2-D array
public static boolean testGrid(char[][] testGrid,
                               char[][] Grid, int N,
                               int M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if (Grid[i][j] != '*')
            {
                if (Grid[i][j] != testGrid[i][j])
                {
                    return false;
                }
            }
        }
    }
    return true;
}
 
// Function to print the grid, if possible
public static void printGrid(char[][] grid, int N,
                             int M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            System.out.print(grid[i][j] + " ");
        }
        System.out.println();
    }
}
 
// Function to check if the grid
// can be made alternating or not
public static void findPossibleGrid(int N, int M,
                                    char[][] grid)
{
     
    // Grids to store the possible grids
    char[][] gridTest1 = new char[N][1001];
    char[][] gridTest2 = new char[N][1001];
 
    createGrid(gridTest1, true, N, M);
    createGrid(gridTest2, false, N, M);
 
    if (testGrid(gridTest1, grid, N, M))
    {
        System.out.println("Yes");
        printGrid(gridTest1, N, M);
    }
    else if (testGrid(gridTest2, grid, N, M))
    {
        System.out.println("Yes");
        printGrid(gridTest2, N, M);
    }
    else
    {
        System.out.println("No");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4, M = 4;
    char[][] grid = { { '*', '*', '1', '0' },
                      { '*', '*', '*', '*' },
                      { '*', '*', '*', '*' },
                      { '*', '*', '0', '1' } };
 
    findPossibleGrid(N, M, grid);
}
}
 
// This code is contributed by maddler

Python3

# python 3 program for the above approach
 
# Function to create the possible grids
def createGrid(grid, is1, N, M):
    for i in range(N):
        for j in range(M):
            if (is1):
                grid[i][j] = '0'
                is1 = False
 
            else:
                grid[i][j] = '1'
                is1 = True
 
        if (M % 2 == 0):
            is1 = True if is1 == False else False
 
# Function to test if any one of them
# matches with the given 2-D array
def testGrid(testGrid, Grid, N, M):
    for i in range(N):
        for j in range(M):
            if (Grid[i][j] != '*'):
                if (Grid[i][j] != testGrid[i][j]):
                    return False
 
    return True
 
# Function to print the grid, if possible
def printGrid(grid, N, M):
    for i in range(N):
        for j in range(M):
            print(grid[i][j],end = " ")
        print("\n",end = "")
 
# Function to check if the grid
# can be made alternating or not
def findPossibleGrid(N, M, grid):
    # Grids to store the possible grids
    gridTest1 = [['' for i in range(1001)] for j in range(N)]
    gridTest2 = [['' for i in range(1001)] for j in range(N)]
 
    createGrid(gridTest1, True, N, M)
 
    createGrid(gridTest2, False, N, M)
 
    if(testGrid(gridTest1, grid, N, M)):
        print("Yes")
        printGrid(gridTest1, N, M)
 
    elif(testGrid(gridTest2, grid, N, M)):
        print("Yes")
        printGrid(gridTest2, N, M)
    else:
        print("No")
 
# Driver Code
if __name__ == '__main__':
    N = 4
    M = 4
    grid  = [['*', '*', '1', '0'],
             ['*', '*', '*', '*'],
             ['*', '*', '*', '*'],
             ['*', '*', '0', '1']]
 
    findPossibleGrid(N, M, grid)
     
    # This code is contributed by ipg2016107.

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to create the possible grids
public static void createGrid(char[,] grid,
                              bool is1,
                              int N, int M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if (is1)
            {
                grid[i, j] = '0';
                is1 = false;
            }
            else
            {
                grid[i, j] = '1';
                is1 = true;
            }
        }
        if (M % 2 == 0)
            is1 = !is1;
    }
}
 
// Function to test if any one of them
// matches with the given 2-D array
public static bool testGrid(char[,] testGrid,
                            char[,] Grid, int N,
                            int M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if (Grid[i, j] != '*')
            {
                if (Grid[i, j] != testGrid[i, j])
                {
                    return false;
                }
            }
        }
    }
    return true;
}
 
// Function to print the grid, if possible
public static void printGrid(char[,] grid, int N,
                             int M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            Console.Write(grid[i, j] + " ");
        }
        Console.WriteLine();
    }
}
 
// Function to check if the grid
// can be made alternating or not
public static void findPossibleGrid(int N, int M,
                                    char[,] grid)
{
     
    // Grids to store the possible grids
    char[,] gridTest1 = new char[N, 1001];
    char[,] gridTest2 = new char[N, 1001];
 
    createGrid(gridTest1, true, N, M);
    createGrid(gridTest2, false, N, M);
 
    if (testGrid(gridTest1, grid, N, M))
    {
        Console.WriteLine("Yes");
        printGrid(gridTest1, N, M);
    }
    else if (testGrid(gridTest2, grid, N, M))
    {
        Console.WriteLine("Yes");
        printGrid(gridTest2, N, M);
    }
    else
    {
        Console.WriteLine("No");
    }
}
 
// Driver code
public static void Main()
{
    int N = 4, M = 4;
    char[,] grid = { { '*', '*', '1', '0' },
                     { '*', '*', '*', '*' },
                     { '*', '*', '*', '*' },
                     { '*', '*', '0', '1' } };
     
    findPossibleGrid(N, M, grid);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to create the possible grids
function createGrid(grid, is1, N, M) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (is1) {
        grid[i][j] = "0";
        is1 = false;
      } else {
        grid[i][j] = "1";
        is1 = true;
      }
    }
    if (M % 2 == 0) is1 = !is1;
  }
}
 
// Function to test if any one of them
// matches with the given 2-D array
function testGrid(testGrid, Grid, N, M) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (Grid[i][j] != "*") {
        if (Grid[i][j] != testGrid[i][j]) {
          return false;
        }
      }
    }
  }
  return true;
}
 
// Function to print the grid, if possible
function printGrid(grid, N, M) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      document.write(grid[i][j] + " ");
    }
    document.write("<br>");
  }
}
 
// Function to check if the grid
// can be made alternating or not
function findPossibleGrid(N, M, grid) {
  // Grids to store the possible grids
  let gridTest1 = new Array(N).fill(0).map(() => new Array(1001));
  let gridTest2 = new Array(N).fill(0).map(() => new Array(1001));
 
  createGrid(gridTest1, true, N, M);
 
  createGrid(gridTest2, false, N, M);
 
  if (testGrid(gridTest1, grid, N, M)) {
    document.write("Yes<br>");
    printGrid(gridTest1, N, M);
  } else if (testGrid(gridTest2, grid, N, M)) {
    document.write("Yes<br>");
    printGrid(gridTest2, N, M);
  } else {
    document.write("No<br>");
  }
}
 
// Driver Code
 
let N = 4,
  M = 4;
let grid = [
  ["*", "*", "1", "0"],
  ["*", "*", "*", "*"],
  ["*", "*", "*", "*"],
  ["*", "*", "0", "1"],
];
 
findPossibleGrid(N, M, grid);
 
</script>
Producción

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

Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)

Enfoque eficiente: la idea es usar dos variables en lugar de crear arrays 2-D para mantener las posibles arrays alternas. Siga los pasos a continuación para resolver el problema:

  • Defina una función posCheck(char grid[][1001], int N, int M, char check) y realice las siguientes tareas:
    • Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
      • Itere sobre el rango [0, M] usando la variable j y realizando las siguientes tareas:
        • Si grid[i][j] es igual a ‘*’, entonces continúe .
        • De lo contrario, si (i+j)%2 es igual a 1 y grid[i][j] no es igual a check , entonces devuelve false.
        • De lo contrario, si (i+j)%2 es igual a 0 y grid[i][j] es igual a check , entonces devuelve false.
    • Después de realizar los pasos anteriores, devuelve el valor de verdadero como respuesta.
  • Defina una función posCheck(char grid[][1001], int N, int M, char impar, char even) y realice las siguientes tareas:
    • Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
      • Itere sobre el rango [0, M] usando la variable j y realizando las siguientes tareas:
        • Si (i+j)%2 es igual a 1, establezca el valor de grid[i][j] en impar o par.
  • Inicialice el indicador de variable bool como verdadero.
  • Inicialice las variables k y o como -1 para almacenar el valor de la primera celda que no tiene el carácter ‘*’.
  • Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
    • Itere sobre el rango [0, M] usando la variable j y realizando las siguientes tareas:
      • Si Grid[i][j] no es igual a ‘*’, establezca el valor de k como i y o como j y rompa .
    • Si k no es igual a -1, entonces rompa .
  • Si k no es igual a -1, llame a la función PosCheck(grid, n, m, ‘1’) y almacene el valor devuelto por la función en la variable flag y si flag es verdadero, llame a la función fill(grid , n, m, ‘1’, ‘0’) para llenar la cuadrícula de una de las formas posibles.
  • Si la bandera es falsa, llame a la función PosCheck (cuadrícula, n, m, ‘0’) y almacene el valor devuelto por la función en la variable bandera y si la bandera es verdadera, llame a la función llenar (cuadrícula, n, m , ‘0’, ‘1’) para llenar la cuadrícula de una de las formas posibles.
  • Si k es igual a -1, entonces, inicialice la variable char h como ‘0’ .
  • Itere sobre el rango [0, M] usando la variable i y realizando las siguientes tareas:
    • Establezca el valor de grid[0][i] como h y si h es ‘ 0 ‘, configúrelo en ‘ 1 ‘, de lo contrario, ‘0’.
  • Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
    • Itere sobre el rango [0, M] usando la variable j y realizando las siguientes tareas:
      • Si i-1 es menor que 0 , continúe .
      • Si grid[i-1][j] es ‘1’, configúrelo en ‘0’, de lo contrario , ‘1’.
  • Establezca el valor de la bandera como verdadero ya que la cuadrícula se alterna .
  • Si la bandera es falsa, imprima «NO» .
  • De lo contrario, imprima “SÍ” e imprima los elementos de la grilla[][].

A continuación se muestra la implementación del enfoque anterior. 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check for the grid in
// one of the alternating ways
bool PosCheck(char a[][1001], int n,
              int m, char check)
{
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Iterate over the range
        for (int j = 0; j < m; j++) {
 
            if (a[i][j] == '*') {
                continue;
            }
            else {
 
                // (i+j)%2==1 cells should be with
                // the character check and the rest
                // should be with the other character
                if (((i + j) & 1) && a[i][j] != check) {
                    return false;
                }
                if (!((i + j) & 1) && a[i][j] == check) {
                    return false;
                }
            }
        }
    }
    return true;
}
 
// Function to fill the grid in a possible way
void fill(char a[][1001], int n, int m,
          char odd, char even)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((i + j) & 1) {
                a[i][j] = odd;
            }
            else {
                a[i][j] = even;
            }
        }
    }
}
 
// Function to find if the grid can be made alternating
void findPossibleGrid(int n, int m, char a[][1001])
{
    bool flag = true;
    int k = -1, o = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            if (a[i][j] != '*') {
 
                // If grid contains atleast
                // one 1 or 0
                k = i;
                o = j;
                break;
            }
        }
        if (k != -1) {
            break;
        }
    }
    if (k != -1) {
        flag = PosCheck(a, n, m, '1');
        if (flag) {
            fill(a, n, m, '1', '0');
        }
        else {
            flag = PosCheck(a, n, m, '0');
            if (flag) {
                fill(a, n, m, '0', '1');
            }
        }
    }
    else {
        // Fill the grid in any possible way
        char h = '1';
        for (int i = 0; i < m; i++) {
            a[0][i] = h;
            if (h == '1') {
                h = '0';
            }
            else {
                h = '1';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i - 1 < 0) {
                    continue;
                }
                if (a[i - 1][j] == '1') {
                    a[i][j] = '0';
                }
                else {
                    a[i][j] = '1';
                }
            }
        }
        flag = true;
    }
 
    if (!flag) {
        cout << "NO\n";
    }
    else {
        cout << "YES\n";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << a[i][j];
            }
            cout << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int n = 4, m = 4;
    char grid[][1001] = { { '*', '*', '1', '0' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '0', '1' } };
 
    findPossibleGrid(n, m, grid);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static boolean PosCheck(char[][] a, int n, int m,
                                   char check)
    {
 
        // Iterate over the range
        for (int i = 0; i < n; i++) {
 
            // Iterate over the range
            for (int j = 0; j < m; j++) {
 
                if (a[i][j] == '*') {
                    continue;
                }
                else {
 
                    // (i+j)%2==1 cells should be with
                    // the character check and the rest
                    // should be with the other character
                    if ((((i + j) & 1) == 1)
                        && a[i][j] != check) {
                        return false;
                    }
                    if (!(((i + j) & 1) == 1)
                        && a[i][j] == check) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
 
    // Function to fill the grid in a possible way
    public static void fill(char[][] a, int n, int m,
                            char odd, char even)
    {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (((i + j) & 1) == 1) {
                    a[i][j] = odd;
                }
                else {
                    a[i][j] = even;
                }
            }
        }
    }
 
    // Function to find if the grid can be made alternating
    public static void findPossibleGrid(int n, int m,
                                        char[][] a)
    {
        boolean flag = true;
        int k = -1, o = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
 
                if (a[i][j] != '*') {
 
                    // If grid contains atleast
                    // one 1 or 0
                    k = i;
                    o = j;
                    break;
                }
            }
            if (k != -1) {
                break;
            }
        }
        if (k != -1) {
            flag = PosCheck(a, n, m, '1');
            if (flag) {
                fill(a, n, m, '1', '0');
            }
            else {
                flag = PosCheck(a, n, m, '0');
                if (flag) {
                    fill(a, n, m, '0', '1');
                }
            }
        }
        else {
            // Fill the grid in any possible way
            char h = '1';
            for (int i = 0; i < m; i++) {
                a[0][i] = h;
                if (h == '1') {
                    h = '0';
                }
                else {
                    h = '1';
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i - 1 < 0) {
                        continue;
                    }
                    if (a[i - 1][j] == '1') {
                        a[i][j] = '0';
                    }
                    else {
                        a[i][j] = '1';
                    }
                }
            }
            flag = true;
        }
 
        if (!flag) {
            System.out.println("No");
        }
        else {
            System.out.println("Yes");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    System.out.print(a[i][j]);
                }
                System.out.println();
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 4, m = 4;
        char[][] grid = { { '*', '*', '1', '0' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '0', '1' } };
 
        findPossibleGrid(n, m, grid);
    }
}
 
// This code is contributed by maddler.

Python3

# Python program for the above approach
 
# Function to check for the grid in
# one of the alternating ways
def PosCheck(a, n, m, check):
 
  # Iterate over the range
  for i in range(n):
   
    # Iterate over the range
    for j in range(m):
 
        if (a[i][j] == "*"):
            continue
        else:
       
            # (i+j)%2==1 cells should be with
            # the character check and the rest
            # should be with the other character
            if (((i + j) & 1) and a[i][j] != check):
                return False
            if (((i + j) & 1) == 0 and a[i][j] == check):
                return False
    return True
 
# Function to fill the grid in a possible way
def fill(a, n, m, odd, even):
     
    for i in range(n):
        for j in range(m):
            if ((i + j) & 1):
                a[i][j] = odd
            else:
                a[i][j] = even
 
# Function to find if the grid can be made alternating
def findPossibleGrid(n, m, a):
    flag,k,O = True,-1,-1
    for i in range(n):
        for j in range(m):
            if (a[i][j] != "*"):
       
                # If grid contains atleast
                # one 1 or 0
                k = i
                O = j
                break
 
        if (k != -1):
            break
    if (k != -1):
        flag = PosCheck(a, n, m, "1")
        if (flag):
            fill(a, n, m, "1", "0")
        else:
            flag = PosCheck(a, n, m, "0")
            if (flag):
                fill(a, n, m, "0", "1")
    else:
   
        # Fill the grid in any possible way
        h = "1"
        for i in range(m):
            a[0][i] = h
            if (h == "1"):
                h = "0"
            else:
                h = "1"
        for i in range(n):
            for j in range(m):
                if (i - 1 < 0):
                    continue
                if (a[i - 1][j] == "1"):
                    a[i][j] = "0"
                else:
                    a[i][j] = "1"
        flag = True
 
    if (flag == 0):
        print("NO")
    else:
        print("YES")
         
        for i in range(n):
            for j in range(m):
                print(a[i][j],end="")
            print()
 
# Driver Code
n,m = 4,4
grid = [
  ["*", "*", "1", "0"],
  ["*", "*", "*", "*"],
  ["*", "*", "*", "*"],
  ["*", "*", "0", "1"],
]
 
findPossibleGrid(n, m, grid)
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
    public static bool PosCheck(char[,] a, int n, int m,
                                   char check)
    {
 
        // Iterate over the range
        for (int i = 0; i < n; i++) {
 
            // Iterate over the range
            for (int j = 0; j < m; j++) {
 
                if (a[i, j] == '*') {
                    continue;
                }
                else {
 
                    // (i+j)%2==1 cells should be with
                    // the character check and the rest
                    // should be with the other character
                    if ((((i + j) & 1) == 1)
                        && a[i, j] != check) {
                        return false;
                    }
                    if (!(((i + j) & 1) == 1)
                        && a[i, j] == check) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
 
    // Function to fill the grid in a possible way
    public static void fill(char[,] a, int n, int m,
                            char odd, char even)
    {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (((i + j) & 1) == 1) {
                    a[i, j] = odd;
                }
                else {
                    a[i, j] = even;
                }
            }
        }
    }
 
    // Function to find if the grid can be made alternating
    public static void findPossibleGrid(int n, int m,
                                        char[,] a)
    {
        bool flag = true;
        int k = -1, o = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
 
                if (a[i, j] != '*') {
 
                    // If grid contains atleast
                    // one 1 or 0
                    k = i;
                    o = j;
                    break;
                }
            }
            if (k != -1) {
                break;
            }
        }
        if (k != -1) {
            flag = PosCheck(a, n, m, '1');
            if (flag) {
                fill(a, n, m, '1', '0');
            }
            else {
                flag = PosCheck(a, n, m, '0');
                if (flag) {
                    fill(a, n, m, '0', '1');
                }
            }
        }
        else {
            // Fill the grid in any possible way
            char h = '1';
            for (int i = 0; i < m; i++) {
                a[0, i] = h;
                if (h == '1') {
                    h = '0';
                }
                else {
                    h = '1';
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i - 1 < 0) {
                        continue;
                    }
                    if (a[i - 1, j] == '1') {
                        a[i, j] = '0';
                    }
                    else {
                        a[i, j] = '1';
                    }
                }
            }
            flag = true;
        }
 
        if (!flag) {
            Console.WriteLine("No");
        }
        else {
            Console.WriteLine("Yes");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    Console.Write(a[i, j]);
                }
                Console.WriteLine();
            }
        }
    }
 
// Driver Code
public static void Main()
{
        int n = 4, m = 4;
        char[,] grid = { { '*', '*', '1', '0' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '*', '*' },
                          { '*', '*', '0', '1' } };
 
        findPossibleGrid(n, m, grid);
}
}
 
// This code is contributed by splevel62.

Javascript

<script>
// Javascript program for the above approach
 
// Function to check for the grid in
// one of the alternating ways
function PosCheck(a, n, m, check)
{
 
  // Iterate over the range
  for (let i = 0; i < n; i++)
  {
   
    // Iterate over the range
    for (let j = 0; j < m; j++)
    {
      if (a[i][j] == "*")
      {
        continue;
      }
      else
      {
       
        // (i+j)%2==1 cells should be with
        // the character check and the rest
        // should be with the other character
        if ((i + j) & 1 && a[i][j] != check) {
          return false;
        }
        if (!((i + j) & 1) && a[i][j] == check) {
          return false;
        }
      }
    }
  }
  return true;
}
 
// Function to fill the grid in a possible way
function fill(a, n, m, odd, even) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if ((i + j) & 1) {
        a[i][j] = odd;
      } else {
        a[i][j] = even;
      }
    }
  }
}
 
// Function to find if the grid can be made alternating
function findPossibleGrid(n, m, a) {
  let flag = true;
  let k = -1,
    o = -1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (a[i][j] != "*")
      {
       
        // If grid contains atleast
        // one 1 or 0
        k = i;
        o = j;
        break;
      }
    }
    if (k != -1) {
      break;
    }
  }
  if (k != -1) {
    flag = PosCheck(a, n, m, "1");
    if (flag) {
      fill(a, n, m, "1", "0");
    } else {
      flag = PosCheck(a, n, m, "0");
      if (flag) {
        fill(a, n, m, "0", "1");
      }
    }
  }
  else
  {
   
    // Fill the grid in any possible way
    let h = "1";
    for (let i = 0; i < m; i++) {
      a[0][i] = h;
      if (h == "1") {
        h = "0";
      } else {
        h = "1";
      }
    }
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (i - 1 < 0) {
          continue;
        }
        if (a[i - 1][j] == "1") {
          a[i][j] = "0";
        } else {
          a[i][j] = "1";
        }
      }
    }
    flag = true;
  }
 
  if (!flag) {
    document.write("NO<br>");
  } else {
    document.write("YES<br>");
    for (let i = 0; i < n; i++)
    {
      for (let j = 0; j < m; j++)
      {
        document.write(a[i][j]);
      }
      document.write("<br>");
    }
  }
}
 
// Driver Code
 
let n = 4,
  m = 4;
let grid = [
  ["*", "*", "1", "0"],
  ["*", "*", "*", "*"],
  ["*", "*", "*", "*"],
  ["*", "*", "0", "1"],
];
 
findPossibleGrid(n, m, grid);
 
// This code is contributed by saurabh_jaiswal.
</script>
Producción

YES
1010
0101
1010
0101

Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por maddler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *