Cree una array espiral de tamaño N * M a partir de una array dada

Posted on by Rudeus Greyrat

Dados dos valores M y N , llene una array de tamaño ‘ M * N ‘ en forma de espiral (o circular) (en el sentido de las agujas del reloj) con elementos de array dados.

Ejemplos:  

Entrada : M = 4, N = 4, arr = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
Salida : 1 2 3 4
             12 13 14 5
            11 16 15 6
            10 9 8 7

Entrada : M = 3, N = 4, arr =[1 8 6 3 8 6 1 6 3 2 5 3]
Salida : 1 8 6 3
               2 5 3 8
              3 6 1 6 

 

Enfoque : El problema anterior se puede resolver utilizando array transversal con condiciones especiales de giro .

La idea es atravesar la array en una dirección e insertar elementos nivel por nivel, hasta llegar a un límite o celda ya llena. Tan pronto como golpees una pared de este tipo, gira a la derecha y continúa igual.

Siga los pasos a continuación

  • Cree una array de tamaño m*n con valor 0 en cada celda inicialmente
  • Atravesaremos un solo bucle de 1 a m*n
  • La dirección del movimiento será decidida por una variable dir con 4 estados:
    • 0 para la derecha,
    • 1 para Abajo,
    • 2 para Izquierda, y
    • 3 para arriba
  • Se accede a la celda actual de array usando i y j como mat[i][j]
  • Para cada dirección, los cambios en i y j serán: 
     

       yo j

R: 0, 1

D: 1, 0

L: 0, -1

U: -1, 0

  • En cada iteración:
    • Rellene mat[i][j] con el valor en el índice actual de la array e incremente el índice actual en 1
    • Luego verifique si el siguiente paso está fuera de los límites o un valor distinto de 0, lo que significa que la celda ya está llena
    • Si la condición anterior es verdadera, cambie la dirección en 1 estado
    • Desplace el puntero i y j según la dirección actual

C++

// C++ program to fill a matrix with values
// from given array in spiral fashion.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the current
// traversing pointer has gone out of bound
bool outOfBound(int i, int n)
{
    if (i < 0 || i >= n)
        return true;
    else
        return false;
}
 
// Function to generate
// m*n circular matrix
vector<vector<int> > spiralFill(
    vector<int>& arr,
    int m, int n)
{
 
    vector<vector<int> > mat(
        n, vector<int>(n, 0));
 
    // Direction:   R D L U
    // dir:         0 1 2 3
    int dir = 0;
 
    // Values to be filled
    // from arr.begin to arr.end
    int value = 0, end = arr.size();
 
    // i  j
    // R:  0, 1
    // D:  1, 0
    // L:  0, -1
    // U: -1, 0
    vector<vector<int> > dirArr;
    dirArr.push_back({ 0, 1 });
    dirArr.push_back({ 1, 0 });
    dirArr.push_back({ 0, -1 });
    dirArr.push_back({ -1, 0 });
 
    // Traversal pointers
    int i = 0, j = 0;
 
    while (value < end) {
 
        // Fill value
        mat[i][j] = arr[value];
 
        // Increment curr value
        value++;
 
        // Make a turn if next step
        // is boundary or a non-0 cell
        if (outOfBound(i + dirArr[dir][0], m)
            || outOfBound(j + dirArr[dir][1], n)
            || mat[i + dirArr[dir][0]]
                  [j + dirArr[dir][1]]
                   != 0) {
            dir = (dir + 1) % 4;
        }
 
        // Position of next cell
        i = i + dirArr[dir][0];
        j = j + dirArr[dir][1];
    }
 
    return mat;
}
 
// Driver program to test above functions
int main()
{
    int m = 3, n = 4;
    vector<int> arr
        = { 1, 8, 6, 3, 8, 6, 1,
            6, 3, 2, 5, 3 };
 
    vector<vector<int> > mat
        = spiralFill(arr, m, n);
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            cout << mat[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
 
  // Function to check if the current
  // traversing pointer has gone out of bound
  static boolean outOfBound(int i, int n)
  {
    if (i < 0 || i >= n)
      return true;
    else
      return false;
  }
 
  // Function to generate
  // m*n circular matrix
  static int[][] spiralFill(int[] arr, int m, int n)
  {
 
    int[][] mat = new int[n][n];
    for (int a = 0; a < n; a++) {
      for (int b = 0; b < n; b++) {
        mat[a][b] = 0;
      }
    }
 
    // Direction:   R D L U
    // dir:         0 1 2 3
    int dir = 0;
 
    // Values to be filled
    // from arr.begin to arr.end
    int value = 0, end = arr.length;
 
    // i  j
    // R:  0, 1
    // D:  1, 0
    // L:  0, -1
    // U: -1, 0
    int[][] dirArr = new int[4][ 2];
    dirArr[0][ 0] = 0;
    dirArr[0][1] = 1;
    dirArr[1][0] = 1;
    dirArr[1][1] = 0;
    dirArr[2][ 0] = 0;
    dirArr[2][1] = -1;
    dirArr[3][0] = -1;
    dirArr[3][1] = 0;
 
    // Traversal pointers
    int i = 0, j = 0;
 
    while (value < end) {
 
      // Fill value
      mat[i][ j] = arr[value];
 
      // Increment curr value
      value++;
 
      // Make a turn if next step
      // is boundary or a non-0 cell
      if (outOfBound(i + dirArr[dir][0], m)
          || outOfBound(j + dirArr[dir][1], n)
          || mat[i + dirArr[dir][0]]
          [j + dirArr[dir][ 1]]
          != 0) {
        dir = (dir + 1) % 4;
      }
 
      // Position of next cell
      i = i + dirArr[dir][ 0];
      j = j + dirArr[dir][1];
    }
 
    return mat;
  }
 
  // Driver program to test above functions
  public static void main (String[] args)
  {
    int m = 3, n = 4;
    int[] arr = { 1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3 };
 
    int[][] mat = spiralFill(arr, m, n);
 
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        System.out.print(mat[i][ j] + " ");
      }
      System.out.println();
    }
  }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python program to fill a matrix with values
# from given array in spiral fashion.
 
# Function to check if the current
# traversing pointer has gone out of bound
def outOfBound(i, n):
    if (i < 0 or i >= n):
        return True
    else:
        return False
 
# Function to generate
# m*n circular matrix
def spiralFill(arr, m, n):
 
    mat = [[0 for col in range(n)]for row in range(n)]
 
    # Direction: R D L U
    # dir: 0 1 2 3
    dir = 0
 
    # Values to be filled
    # from arr.begin to arr.end
    value,end = 0,len(arr)
 
    # i j
    # R: 0, 1
    # D: 1, 0
    # L: 0, -1
    # U: -1, 0
    dirArr = []
    dirArr.append([0, 1])
    dirArr.append([1, 0])
    dirArr.append([0, -1])
    dirArr.append([-1, 0])
 
    # Traversal pointers
    i,j = 0,0
 
    while (value < end):
 
        # Fill value
        mat[i][j] = arr[value]
 
        # Increment curr value
        value += 1
 
        # Make a turn if next step
        # is boundary or a non-0 cell
        if (outOfBound(i + dirArr[dir][0], m) or outOfBound(j + dirArr[dir][1], n) or mat[i + dirArr[dir][0]][j + dirArr[dir][1]]!= 0):
            dir = (dir + 1) % 4
 
        # Position of next cell
        i = i + dirArr[dir][0]
        j = j + dirArr[dir][1]
 
    return mat
 
# Driver program to test above functions
m,n = 3,4
arr = [1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3]
 
mat = spiralFill(arr, m, n)
 
for i in range(m):
    for j in range(n):
        print(mat[i][j],end=" ")
    print()
 
# This code is contributed by shinjanpatra

C#

// C# program to fill a matrix with values
// from given array in spiral fashion.
 
using System;
class GFG {
 
  // Function to check if the current
  // traversing pointer has gone out of bound
  static bool outOfBound(int i, int n)
  {
    if (i < 0 || i >= n)
      return true;
    else
      return false;
  }
 
  // Function to generate
  // m*n circular matrix
  static int[, ] spiralFill(int[] arr, int m, int n)
  {
 
    int[, ] mat = new int[n, n];
    for (int a = 0; a < n; a++) {
      for (int b = 0; b < n; b++) {
        mat[a, b] = 0;
      }
    }
 
    // Direction:   R D L U
    // dir:         0 1 2 3
    int dir = 0;
 
    // Values to be filled
    // from arr.begin to arr.end
    int value = 0, end = arr.Length;
 
    // i  j
    // R:  0, 1
    // D:  1, 0
    // L:  0, -1
    // U: -1, 0
    int[, ] dirArr = new int[4, 2];
    dirArr[0, 0] = 0;
    dirArr[0, 1] = 1;
    dirArr[1, 0] = 1;
    dirArr[1, 1] = 0;
    dirArr[2, 0] = 0;
    dirArr[2, 1] = -1;
    dirArr[3, 0] = -1;
    dirArr[3, 1] = 0;
 
    // Traversal pointers
    int i = 0, j = 0;
 
    while (value < end) {
 
      // Fill value
      mat[i, j] = arr[value];
 
      // Increment curr value
      value++;
 
      // Make a turn if next step
      // is boundary or a non-0 cell
      if (outOfBound(i + dirArr[dir, 0], m)
          || outOfBound(j + dirArr[dir, 1], n)
          || mat[i + dirArr[dir, 0],
                 j + dirArr[dir, 1]]
          != 0) {
        dir = (dir + 1) % 4;
      }
 
      // Position of next cell
      i = i + dirArr[dir, 0];
      j = j + dirArr[dir, 1];
    }
 
    return mat;
  }
 
  // Driver program to test above functions
  public static void Main()
  {
    int m = 3, n = 4;
    int[] arr = { 1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3 };
 
    int[, ] mat = spiralFill(arr, m, n);
 
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        Console.Write(mat[i, j] + " ");
      }
      Console.WriteLine();
    }
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program to fill a matrix with values
    // from given array in spiral fashion.
 
    // Function to check if the current
    // traversing pointer has gone out of bound
    const outOfBound = (i, n) => {
        if (i < 0 || i >= n)
            return true;
        else
            return false;
    }
 
    // Function to generate
    // m*n circular matrix
    const spiralFill = (arr, m, n) => {
 
        let mat = new Array(n).fill(0).map(() => new Array(n).fill(0));
 
        // Direction: R D L U
        // dir:         0 1 2 3
        let dir = 0;
 
        // Values to be filled
        // from arr.begin to arr.end
        let value = 0, end = arr.length;
 
        // i j
        // R: 0, 1
        // D: 1, 0
        // L: 0, -1
        // U: -1, 0
        let dirArr = [];
        dirArr.push([0, 1]);
        dirArr.push([1, 0]);
        dirArr.push([0, -1]);
        dirArr.push([-1, 0]);
 
        // Traversal pointers
        let i = 0, j = 0;
 
        while (value < end) {
 
            // Fill value
            mat[i][j] = arr[value];
 
            // Increment curr value
            value++;
 
            // Make a turn if next step
            // is boundary or a non-0 cell
            if (outOfBound(i + dirArr[dir][0], m)
                || outOfBound(j + dirArr[dir][1], n)
                || mat[i + dirArr[dir][0]]
                [j + dirArr[dir][1]]
                != 0) {
                dir = (dir + 1) % 4;
            }
 
            // Position of next cell
            i = i + dirArr[dir][0];
            j = j + dirArr[dir][1];
        }
 
        return mat;
    }
 
    // Driver program to test above functions
    let m = 3, n = 4;
    let arr = [1, 8, 6, 3, 8, 6, 1,
        6, 3, 2, 5, 3];
 
    let mat = spiralFill(arr, m, n);
 
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++)
            document.write(`${mat[i][j]} `);
        document.write("<br/>");
    }
 
// This code is contributed by rakeshsahni
</script>
Producción

1 8 6 3 
2 5 3 8 
3 6 1 6

Complejidad de Tiempo : O(N*M)
Espacio Auxiliar : O(N*M)

Publicación traducida automáticamente

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