Programa para el Juego de la Vida de Conway | conjunto 2

Posted on by Rudeus Greyrat

Dada una cuadrícula binaria [ ][ ] de tamaño N*M , con cada celda que contiene 0 o 1, donde 1 representa una celda viva y 0 representa una celda muerta . La tarea es generar la próxima generación de celdas según las siguientes reglas:  

  1. Cualquier celda viva con menos de dos vecinos vivos muere debido a la falta de población.
  2. Cualquier celda viva con dos o tres vecinos vivos vive en la próxima generación.
  3. Cualquier celda viva con más de tres vecinos vivos muere debido a la sobrepoblación.
  4. Cualquier célula muerta con exactamente tres vecinos vivos se convierte en una célula viva por reproducción.

Aquí, el vecino de una celda incluye sus celdas adyacentes así como también las diagonales, por lo que para cada celda hay un total de 8 vecinos.
Ejemplos: 

Input: N = 5, M = 10 
0000000000 
0001100000 
0000100000 
0000000000 
0000000000 
Output: 
0000000000 
0001100000 
0001100000 
0000000000 
0000000000 
Explanation: 
The cells at (1, 3), (1, 4) and (2, 4) are alive and have 2 neighbors, 
Entonces, de acuerdo con la Regla 2, viven hasta la próxima generación. 
La celda en (2, 3) está muerta y tiene exactamente 3 vecinos, 
por lo tanto, de acuerdo con la Regla 4, se convierte en una celda viva.
Entrada: N = 4, M = 5 
00000 
01100 
00010 
00000 
Salida: 
00000 
00100 
00100 
00000 
Explicación: 
Las celdas en (1, 1) y (2, 3) tienen solo 1 vecina, 
por lo tanto, de acuerdo con la Regla 1, mueren. 
La celda en (1, 2) está viva y tiene 2 vecinos, 
por lo tanto, de acuerdo con la regla 2, vive en la próxima generación. 
La celda en (2, 2) está muerta y tiene exactamente 3 vecinos, 
por lo que, de acuerdo con la Regla 4, se convierte en una celda viva.

Enfoque ingenuo: 
Ya hemos discutido un enfoque para este problema en Program for Conway’s Game Of Life | conjunto 1 . En este enfoque, se crea un futuro de cuadrícula adicional [ ][ ] de tamaño N*M para almacenar la próxima generación de celdas. 
Complejidad de tiempo: O(N*M)  
Espacio auxiliar: O(N*M)
Enfoque eficiente: 
Es posible un enfoque de espacio optimizado para este problema, que no utiliza espacio adicional. Para cada celda viva , incremente su valor en 1 cada vez que encontremos un vecino vivo para ella. Y, por cada célula muerta, decrementa su valor en 1 cada vez que nos encontramos con un vecino vivo para ello. Ahora, si el valor en una celda es menor a 0, significa que es una celda muerta y si el valor es mayor a 0, es una celda viva, también la magnitud del valor en una celda representará el número de sus celdas vivas . vecinos _ De esta forma, no se requerirá una rejilla extra y se obtiene una solución optimizada en el espacio. Los pasos detallados de este enfoque son los siguientes:
Para la posición actual de la cuadrícula, veremos todos los vecinos.  

  1. Atraviesa toda la cuadrícula.
  2. Si el valor del vecino es >= 1 (es decir, el valor inicial del vecino era 1)
    • Si la celda actual es >= 1 , simplemente incremente el valor de la celda actual en 1. 
      Ahora, la cuadrícula [i][j]> 0 implicará que la cuadrícula inicial [i][j] == 1.
    • De lo contrario, la celda actual es <= 0 , simplemente disminuya el valor de la celda actual en 1. 
      Ahora, la cuadrícula [i][j] <= 0 implicará que la cuadrícula inicial [i][j] == 0.
  3. Ahora, genere la nueva red de generación requerida utilizando la red modificada. 
    • Si el valor de la celda actual es > 0 , hay 3 casos posibles: 
      • Si el valor es < 3, cámbielo a 0.
      • De lo contrario, si el valor es <= 4, cámbielo a 1.
      • De lo contrario, cambie el valor a 0.
    • De lo contrario, el valor de celda actual es <= 0 . 
      • Si el valor es 3, cámbielo a 1.
      • De lo contrario, cámbielo a 0.

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

C++

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
void print(vector<vector<int>> grid)
{
    int p = grid.size(),
    q = grid[0].size();
     
    for (int i = 0; i < p; i++) {
      for (int j = 0; j < q; j++) {
     
        cout << grid[i][j];
     }
    cout << endl;
    }
}       
// Function to check if
// index are not out of grid
static bool save(vector<vector<int> > grid,int row, int col)
{
    return (grid.size() > row && grid[0].size() > col && row >= 0 && col >= 0);
}
    // Function to get New Generation
void solve(vector<vector<int> >& grid)
{
      int p = grid.size(),
        q = grid[0].size();
      int u[] = { 1, -1, 0, 1, -1, 0, 1, -1 };
      int v[] = { 0, 0, -1, -1, -1, 1, 1, 1 };
     for (int i = 0; i < p; i++)
     {
      for (int j = 0; j < q; j++)
      {
      // IF the initial value
      // of the grid(i, j) is 1
      if (grid[i][j] > 0)
      {
        for (int k = 0; k < 8; k++)
        {
          if (save(grid, i + u[k],
                   j + v[k]) &&
                   grid[i + u[k]][j + v[k]] > 0)
          {
            // If initial value > 0,
            // just increment it by 1
            grid[i][j]++;
          }
        }
      }
  
      // IF the initial value
      // of the grid(i, j) is 0
      else
      {
         for (int k = 0; k < 8; k++)
         {
           if (save(grid, i + u[k],
                   j + v[k]) &&
                   grid[i + u[k]][j + v[k]] > 0)
              {
                // If initial value <= 0
                // just decrement it by 1
                grid[i][j]--;
              }
           }
        }
      }
    }
  
    // Generating new Generation.
    // Now the magnitude of the
    // grid will represent number
    // of neighbours
    for (int i = 0; i < p; i++)
      {
          for (int j = 0; j < q; j++)
         {
        // If initial value was 1.
        if (grid[i][j] > 0)
        {
            // Since Any live cell with
          // < 2 live neighbors dies
           if (grid[i][j] < 3)
              grid[i][j] = 0;
  
             // Since Any live cell with
            // 2 or 3 live neighbors live
           else if (grid[i][j] <= 4)
            grid[i][j] = 1;
  
            // Since Any live cell with
             // > 3 live neighbors dies
            else if (grid[i][j] > 4)
              grid[i][j] = 0;
        }
       else
        {
        // Since Any dead cell with
        // exactly 3 live neighbors
        // becomes a live cell
         if (grid[i][j] == -3)
              grid[i][j] = 1;
         else
              grid[i][j] = 0;
            }
        }
     }
}
// Driver code
int main ()
{
  vector<vector<int>> grid = {{0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0},
                  {0, 0, 0, 1, 1,
                   0,0, 0, 0, 0},
                  {0, 0, 0, 0, 1,
                   0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0}};
    
  // Function to generate
  // New Generation inplace
  solve(grid);
  
  // Displaying the grid
  print(grid);
  return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
import java.lang.*;
class GFG{
   
static void print(int[][] grid)
{
  int p = grid.length,
  q = grid[0].length;
 
  for (int i = 0; i < p; i++)
  {
    for (int j = 0; j < q; j++)
    {
      System.out.print(grid[i][j]);
    }
    System.out.println();;
  }
}
 
static boolean save(int[][] grid,
                    int row, int col)
{
  return (grid.length > row &&
          grid[0].length > col &&
          row >= 0 && col >= 0);
}
 
static void solve(int[][] grid)
{
  int p = grid.length,
  q = grid[0].length;
 
  // Possible neighboring
  // indexes
  int u[] = {1, -1, 0, 1,
             -1, 0, 1, -1};
  int v[] = {0, 0, -1, -1,
             -1, 1, 1, 1};
   
  for (int i = 0; i < p; i++)
  {
    for (int j = 0; j < q; j++)
    {
      // IF the initial value
      // of the grid(i, j) is 1
      if (grid[i][j] > 0)
      {
        for (int k = 0; k < 8; k++)
        {
          if (save(grid, i + u[k],
                   j + v[k]) &&
                   grid[i + u[k]][j + v[k]] > 0)
          {
            // If initial value > 0,
            // just increment it by 1
            grid[i][j]++;
          }
        }
      }
 
      // IF the initial value
      // of the grid(i, j) is 0
      else
      {
        for (int k = 0; k < 8; k++)
        {
          if (save(grid, i + u[k],
                   j + v[k]) &&
                   grid[i + u[k]][j + v[k]] > 0)
          {
            // If initial value <= 0
            // just decrement it by 1
            grid[i][j]--;
          }
        }
      }
    }
  }
 
  // Generating new Generation.
  // Now the magnitude of the
  // grid will represent number
  // of neighbours
  for (int i = 0; i < p; i++)
  {
    for (int j = 0; j < q; j++)
    {
      // If initial value was 1.
      if (grid[i][j] > 0)
      {
        // Since Any live cell with
        // < 2 live neighbors dies
        if (grid[i][j] < 3)
          grid[i][j] = 0;
 
        // Since Any live cell with
        // 2 or 3 live neighbors live
        else if (grid[i][j] <= 4)
          grid[i][j] = 1;
 
        // Since Any live cell with
        // > 3 live neighbors dies
        else if (grid[i][j] > 4)
          grid[i][j] = 0;
      }
      else
      {
        // Since Any dead cell with
        // exactly 3 live neighbors
        // becomes a live cell
        if (grid[i][j] == -3)
          grid[i][j] = 1;
        else
          grid[i][j] = 0;
      }
    }
  }
}
 
// Driver code
public static void main (String[] args)
{
  int[][] grid = {{0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0},
                  {0, 0, 0, 1, 1,
                   0,0, 0, 0, 0},
                  {0, 0, 0, 0, 1,
                   0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0},
                  {0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0}};
   
  // Function to generate
  // New Generation inplace
  solve(grid);
 
  // Displaying the grid
  print(grid);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 implementation of
# the above approach
 
def print2dArr(grid):
    p = len(grid)
    q = len(grid[0])
 
    for i in range(p):
        for j in range(q):
            print(grid[i][j], end='')
 
        print()
 
 
# Function to check if
# index are not out of grid
def save(grid, row, col):
    return (len(grid) > row and len(grid[0]) > col and row >= 0 and col >= 0)
 
# Function to get New Generation
 
 
def solve(grid):
    p = len(grid)
    q = len(grid[0])
    u = [1, -1, 0, 1, -1, 0, 1, -1]
    v = [0, 0, -1, -1, -1, 1, 1, 1]
    for i in range(p):
        for j in range(q):
            # IF the initial value
            # of the grid(i, j) is 1
            if (grid[i][j] > 0):
                for k in range(8):
                    if (save(grid, i + u[k], j + v[k]) and grid[i + u[k]][j + v[k]] > 0):
                        # If initial value > 0,
                        # just increment it by 1
                        grid[i][j] += 1
 
            # IF the initial value
            # of the grid(i, j) is 0
            else:
                for k in range(8):
                    if (save(grid, i + u[k], j + v[k]) and grid[i + u[k]][j + v[k]] > 0):
                        # If initial value <= 0
                        # just decrement it by 1
                        grid[i][j] -= 1
    # Generating new Generation.
    # Now the magnitude of the
    # grid will represent number
    # of neighbours
    for i in range(p):
        for j in range(q):
            # If initial value was 1.
            if (grid[i][j] > 0):
                # Since Any live cell with
                # < 2 live neighbors dies
                if (grid[i][j] < 3):
                    grid[i][j] = 0
 
                # Since Any live cell with
                # 2 or 3 live neighbors live
                elif (grid[i][j] <= 4):
                    grid[i][j] = 1
 
                # Since Any live cell with
                # > 3 live neighbors dies
                elif (grid[i][j] > 4):
                    grid[i][j] = 0
 
            else:
                # Since Any dead cell with
                # exactly 3 live neighbors
                # becomes a live cell
                if (grid[i][j] == -3):
                    grid[i][j] = 1
                else:
                    grid[i][j] = 0
 
 
# Driver code
if __name__ == '__main__':
    grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ], ]
 
    # Function to generate
    # New Generation inplace
    solve(grid)
 
    # Displaying the grid
    print2dArr(grid)

C#

// C# program for
// the above approach
using System;
using System.Text;
 
public class GFG{
 
  static void print(int[,] grid)
  {
    int p = grid.GetLength(0), q = grid.GetLength(1);
 
    for (int i = 0; i < p; i++)
    {
      for (int j = 0; j < q; j++)
      {
        Console.Write(grid[i,j]);
      }
      Console.Write("\n");
    }
  }
 
  static bool save(int[,] grid,int row, int col)
  {
    return (grid.GetLength(0) > row && grid.GetLength(1) > col && row >= 0 && col >= 0);
  }
 
  static void solve(int[,] grid)
  {
    int p = grid.GetLength(0), q = grid.GetLength(1);
 
    // Possible neighboring
    // indexes
    int[] u = {1, -1, 0, 1, -1, 0, 1, -1};
    int[] v = {0, 0, -1, -1, -1, 1, 1, 1};
 
    for (int i = 0; i < p; i++)
    {
      for (int j = 0; j < q; j++)
      {
        // IF the initial value
        // of the grid(i, j) is 1
        if (grid[i,j] > 0)
        {
          for (int k = 0; k < 8; k++)
          {
            if (save(grid, i + u[k], j + v[k]) && grid[(i + u[k]),(j + v[k])] > 0)
            {
              // If initial value > 0,
              // just increment it by 1
              grid[i,j]++;
            }
          }
        }
 
        // IF the initial value
        // of the grid(i, j) is 0
        else
        {
          for (int k = 0; k < 8; k++)
          {
            if (save(grid, i + u[k], j + v[k]) && grid[(i + u[k]),(j + v[k])] > 0)
            {
              // If initial value <= 0
              // just decrement it by 1
              grid[i,j]--;
            }
          }
        }
      }
    }
 
    // Generating new Generation.
    // Now the magnitude of the
    // grid will represent number
    // of neighbours
    for (int i = 0; i < p; i++)
    {
      for (int j = 0; j < q; j++)
      {
        // If initial value was 1.
        if (grid[i,j] > 0)
        {
          // Since Any live cell with
          // < 2 live neighbors dies
          if (grid[i,j] < 3)
            grid[i,j] = 0;
 
          // Since Any live cell with
          // 2 or 3 live neighbors live
          else if (grid[i,j] <= 4)
            grid[i,j] = 1;
 
          // Since Any live cell with
          // > 3 live neighbors dies
          else if (grid[i,j] > 4)
            grid[i,j] = 0;
        }
        else
        {
          // Since Any dead cell with
          // exactly 3 live neighbors
          // becomes a live cell
          if (grid[i,j] == -3)
            grid[i,j] = 1;
          else
            grid[i,j] = 0;
        }
      }
    }
  }
 
  //Driver Code
  static public void Main (){
 
    int[,] grid = {{0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0},
                   {0, 0, 0, 1, 1,
                    0,0, 0, 0, 0},
                   {0, 0, 0, 0, 1,
                    0, 0, 0, 0, 0},
                   {0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0},
                   {0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0}};
 
    // Function to generate
    // New Generation inplace
    solve(grid);
 
    // Displaying the grid
    print(grid);
 
  }
}
 
// This code is contributed by shruti456rawal

Javascript

<script>
 
// JavaScript implementation of
// the above approach
 
function print2dArr(grid){
    let p = grid.length
    let q = grid[0].length
 
    for(let i=0;i<p;i++){
        for(let j=0;j<q;j++){
            document.write(grid[i][j],'')
        }
        document.write("</br>")
    }
}
 
 
// Function to check if
// index are not out of grid
function save(grid, row, col){
    return grid.length > row && grid[0].length > col && row >= 0 && col >= 0
}
 
// Function to get New Generation
 
 
function solve(grid){
    let p = grid.length
    let q = grid[0].length
    let u = [1, -1, 0, 1, -1, 0, 1, -1]
    let v = [0, 0, -1, -1, -1, 1, 1, 1]
    for(let i = 0; i < p; i++)
    {
        for(let j = 0; j < q; j++)
        {
         
            // IF the initial value
            // of the grid(i, j) is 1
            if (grid[i][j] > 0)
            {
                for(let k = 0; k < 8; k++)
                {
                    if (save(grid, i + u[k], j + v[k]) && grid[i + u[k]][j + v[k]] > 0)
                     
                        // If initial value > 0,
                        // just increment it by 1
                        grid[i][j] += 1
                }
            }
 
            // IF the initial value
            // of the grid(i, j) is 0
            else{
                for(let k = 0;k<8;k++){
                    if (save(grid, i + u[k], j + v[k]) && grid[i + u[k]][j + v[k]] > 0)
                        // If initial value <= 0
                        // just decrement it by 1
                        grid[i][j] -= 1
                }
            }
        }
    }
     
    // Generating new Generation.
    // Now the magnitude of the
    // grid will represent number
    // of neighbours
    for(let i = 0; i < p; i++)
    {
        for(let j = 0; j < q; j++)
        {
         
            // If initial value was 1.
            if (grid[i][j] > 0){
                // Since Any live cell with
                // < 2 live neighbors dies
                if (grid[i][j] < 3)
                    grid[i][j] = 0
 
                // Since Any live cell with
                // 2 or 3 live neighbors live
                else if(grid[i][j] <= 4)
                    grid[i][j] = 1
 
                // Since Any live cell with
                // > 3 live neighbors dies
                else if(grid[i][j] > 4)
                    grid[i][j] = 0
            }
 
            else{
                // Since Any dead cell with
                // exactly 3 live neighbors
                // becomes a live cell
                if (grid[i][j] == -3)
                    grid[i][j] = 1
                else
                    grid[i][j] = 0
            }
        }
    }
}
 
 
// Driver code
 
let    grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ], ]
 
// Function to generate
// New Generation inplace
solve(grid)
 
// Displaying the grid
print2dArr(grid)
 
 
// This code is contributed by shinjanpatra
 
</script>
Producción: 

0000000000
0001100000
0001100000
0000000000
0000000000

 

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

Publicación traducida automáticamente

Artículo escrito por ssatyanand7 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 *