Forme un rectángulo a partir de los elementos de contorno de Matrix usando la lista enlazada

Dada una cuadrícula Matrix [][] de tamaño NxM donde N es el número de filas y M es el número de columnas. La tarea es formar un rectángulo a partir de los elementos límite de grid[][] usando una lista enlazada que tiene cuatro punteros, a saber , anterior , siguiente , superior e inferior . Imprima la lista enlazada final. 

Ejemplos:

Entrada: A = [[13, 42, 93, 88], 
                  [26, 38, 66, 42], 
                 [75, 63, 78, 12]]
Salida: 13 42 93 88 42 12 78 63 75 26

Explicación:  
 

1. Haga A[0][0] y el Node principal
2. Recorra la fila 0 y cree un Node para cada elemento y conéctelos a través del siguiente puntero.
3. Atraviese la columna (m-1) y cree un Node para cada elemento y conéctelos a través del puntero inferior.
4. Atraviese la fila (n-1) y cree un Node para cada elemento y conéctelos a través del puntero anterior.
5. Recorra la columna 0 y cree un Node para cada elemento y conéctelos a través del puntero superior.
6. Los pasos 2, 3, 4, 5 se repiten hasta temp. La parte superior se vuelve igual a la cabeza.

Entrada: A = [[1, 2, 3]
                  [8, 9, 4]
                 [7, 6, 5]]
Salida: 1 2 3 4 5 6 7 8

Enfoque: este problema se puede resolver realizando un cruce de límites de la array y creando Nodes para cada elemento y vinculándolos usando siguiente, anterior, inferior o superior y creando una lista vinculada. 

Siga los pasos a continuación:

Paso 1: haga grid[0][0] como el encabezado de la lista Vinculada e inicialice temp como el encabezado .
Paso 2: recorra la primera fila de j=1 a j=m-1 donde i=0 y cree un Node para cada elemento y vincúlelos a través del siguiente puntero.
Paso 3: Recorra la última columna desde i=0 hasta i=n-1 donde j=m-1 y cree un Node para cada elemento y vincúlelos a través de un puntero inferior .
Paso 4: atravesar la última fila desde j=m-1a j=0 donde i=n-1 y cree un Node para cada elemento y vincúlelos a través del puntero anterior .
Paso 5: recorra la primera columna desde i=n-1 hasta i=0 donde j=0 y cree un Node para cada elemento y vincúlelos a través del puntero superior .
Paso 6: Los pasos 2, 3, 4, 5 se repiten hasta que temp.top sea igual a head .
Paso 7: Imprima la Lista Vinculada requerida.

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

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Node Class
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node* top;
    Node* bottom;
 
    // Constructor to initialize the node object
    Node(int data)
    {
        this->data = data;
        next = NULL;
        prev = NULL;
        top = NULL;
        bottom = NULL;
    }
};
 
// Linked List class
struct LinkedList {
 
    // initialize head
    Node* head = NULL;
 
    // function to form square
    // linked list of matrix.
    void Quad(vector<vector<int> > grid, int n, int m)
    {
 
        // initialising A[0][0] as head.
        head = new Node(grid[0][0]);
 
        // head is assigned to head.
        Node* temp = head;
 
        // i is row index, j is column index
        int i = 0;
        int j = 1;
 
        // loop till temp.top become equal to head.
        while (temp != NULL and temp->top != head) {
            // as we iterating over boundary
            // of matrix so we will iterate
            // over first(0) and last(n-1) row
            // and first(0) and last(m-1) column.
 
            // iterating over first i.e 0th row
            // and connecting node.
            if (j < m && i == 0) {
                temp->next = new Node(grid[i][j]);
                temp = temp->next;
                j += 1;
            }
 
            // iterating over last i.e (m-1)th
            // column and connecting Node.
            else if (j == m && i < n - 1) {
                i = i + 1;
                temp->bottom = new Node(grid[i][j - 1]);
                temp = temp->bottom;
            }
 
            // iterating over last i.e (n-1)th row
            // and connecting Node.
            else if (i == n - 1 && j <= m && j >= 1) {
                if (j == m)
                    j = j - 1;
                j = j - 1;
                temp->prev = new Node(grid[i][j]);
                temp = temp->prev;
            }
 
            // iterating over first i.e 0th column
            // and connecting Node.
            else if (i <= n - 1 && j == 0) {
                i = i - 1;
                temp->top = new Node(grid[i][j]);
                temp = temp->top;
                if (i == 1)
                    temp->top = head;
            }
        }
    }
 
    // function to print Linked list.
    void printList(Node* root)
    {
 
        Node* temp = root;
 
        // printing head of linked list
        cout << temp->data << " ";
 
        // loop till temp.top
        // become equal to head
        while (temp->top != root) {
 
            // printing the node
            if (temp->next) {
                cout << temp->next->data << " ";
                temp = temp->next;
            }
            if (temp->prev) {
                cout << temp->prev->data << " ";
                temp = temp->prev;
            }
            if (temp->bottom) {
                cout << temp->bottom->data << " ";
                temp = temp->bottom;
            }
            if (temp->top) {
                cout << temp->top->data << " ";
                temp = temp->top;
            }
        }
    }
};
 
// Driver Code
int main()
{
    vector<vector<int> > grid = { { 13, 42, 93, 88 },
                                  { 26, 38, 66, 42 },
                                  { 75, 63, 78, 12 } };
 
    // n is number of rows
    int n = grid.size();
     
    // m is number of columns
    int m = grid[0].size();
   
    // creation of object
    LinkedList* l = new LinkedList();
 
    // Call Quad method to create Linked List.
    l->Quad(grid, n, m);
 
    // Call Quad method to create Linked List.
    l->printList(l->head);
 
    return 0;
}
 
// The code is contributed by Gautam goel (gautamgoel962)

Java

// Java program for above approach
 
// Node Class
class Node {
    int data;
    Node next;
    Node prev;
    Node top;
    Node bottom;
    // Constructor to initialize the node object
    Node(int data)
    {
        this.data = data;
        next = null;
        prev = null;
        top = null;
        bottom = null;
    }
}
 
class GFG {
 
    // initialize head
    public Node head = null;
 
    // function to form square linked list of matrix.
    public void Quad(int[][] grid, int n, int m)
    {
 
        // initialising A[0][0] as head.
        head = new Node(grid[0][0]);
 
        // head is assigned to head.
        Node temp = head;
 
        // i is row index, j is column index
        int i = 0;
        int j = 1;
 
        // loop till temp.top become equal to head.
        while (temp.top != head) {
            // as we iterating over boundary
            // of matrix so we will iterate
            // over first(0) and last(n-1) row
            // and first(0) and last(m-1) column.
 
            // iterating over first i.e 0th row
            // and connecting node.
            if (j < m && i == 0) {
                temp.next = new Node(grid[i][j]);
                temp = temp.next;
                j += 1;
            }
 
            // iterating over last i.e (m-1)th
            // column and connecting Node.
            else if (j == m && i < n - 1) {
                i = i + 1;
                temp.bottom = new Node(grid[i][j - 1]);
                temp = temp.bottom;
            }
 
            // iterating over last i.e (n-1)th row
            // and connecting Node.
            else if (i == n - 1 && j <= m && j >= 1) {
                if (j == m) {
                    j = j - 1;
                }
                j = j - 1;
                temp.prev = new Node(grid[i][j]);
                temp = temp.prev;
            }
 
            // iterating over first i.e 0th column
            // and connecting Node.
            else if (i <= n - 1 && j == 0) {
                i = i - 1;
                temp.top = new Node(grid[i][j]);
                temp = temp.top;
                if (i == 1) {
                    temp.top = head;
                }
            }
        }
    }
 
    // function to print Linked list.
    public void printList(Node root)
    {
        Node temp = root;
 
        // printing head of linked list
        System.out.print(temp.data + " ");
 
        // loop till temp.top
        // become equal to head
        while (temp.top != root) {
 
            // printing the node
            if (temp.next != null) {
                System.out.print(temp.next.data + " ");
                temp = temp.next;
            }
            if (temp.prev != null) {
                System.out.print(temp.prev.data + " ");
                temp = temp.prev;
            }
            if (temp.bottom != null) {
                System.out.print(temp.bottom.data + " ");
                temp = temp.bottom;
            }
            if (temp.top != null) {
                System.out.print(temp.top.data + " ");
                temp = temp.top;
            }
        }
    }
 
    public static void main(String[] args)
    {
 
        int[][] grid = new int[][] { { 13, 42, 93, 88 },
                                     { 26, 38, 66, 42 },
                                     { 75, 63, 78, 12 } };
 
        // n is number of rows
        int n = grid.length;
 
        // m is number of columns
        int m = grid[0].length;
 
        GFG l = new GFG();
 
        // Call Quad method to create Linked List.
        l.Quad(grid, n, m);
 
        // Call Quad method to create Linked List.
        l.printList(l.head);
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

Python3

# Python program for above approach
# Node Class
class Node:
 
    # Constructor to initialize the node object
    def __init__(self, val):
        self.data = val
        self.next = None
        self.prev = None
        self.top = None
        self.bottom = None
 
 
# Linked List class
class LinkedList:
 
    # Constructor to initialize head
    def __init__(self):
        self.head = None
 
    # function to form square
    # linked list of matrix.
    def Quad(self, grid, n, m):
 
        # initialising A[0][0] as head.
        self.head = Node(grid[0][0])
 
        # head is assigned to head.
        temp = self.head
 
        # i is row index, j is column index
        i = 0
        j = 1
 
        # loop till temp.top become equal to head.
        while temp.top != self.head:
            # as we iterating over boundary
            # of matrix so we will iterate
            # over first(0) and last(n-1) row
            # and first(0) and last(m-1) column.
 
            # iterating over first i.e 0th row
            # and connecting node.
            if j < m and i == 0:
                temp.next = Node(grid[i][j])
                temp = temp.next
                j += 1
 
            # iterating over last i.e (m-1)th
            # column and connecting Node.
            elif j == m and i < n - 1:
                i = i + 1
                temp.bottom = Node(grid[i][j - 1])
                temp = temp.bottom
 
            # iterating over last i.e (n-1)th row
            # and connecting Node.
            elif i == n - 1 and j <= m and j >= 1:
                if j == m: j = j - 1
                j = j - 1
                temp.prev = Node(grid[i][j])
                temp = temp.prev
 
            # iterating over first i.e 0th column
            # and connecting Node.
            elif i <= n - 1 and j == 0:
                i = i - 1
                temp.top = Node(grid[i][j])
                temp = temp.top
                if i == 1:
                    temp.top = self.head
 
    # function to print Linked list.
    def printList(self, root):
         
        temp = root
         
        # printing head of linked list
        print(temp.data, end =" ")
         
        # loop till temp.top
        # become equal to head
        while temp.top != root:
           
          # printing the node
            if temp.next:
                print(temp.next.data, end =" ")
                temp = temp.next
            if temp.prev:
                print(temp.prev.data, end =" ")
                temp = temp.prev
            if temp.bottom:
                print(temp.bottom.data, end =" ")
                temp = temp.bottom
            if temp.top:
                print(temp.top.data, end =" ")
                temp = temp.top
 
# Driver Code
grid = [[13, 42, 93, 88],   
        [26, 38, 66, 42],
        [75, 63, 78, 12]]
 
# n is number of rows
n = len(grid)
 
# m is number of column
m = len(grid[0])
 
# creation of object
l = LinkedList()
 
# Call Quad method to create Linked List.
l.Quad(grid, n, m)
 
# Call printList method to print list.
l.printList(l.head)

Javascript

<script>
// Javascript program for above approach
// Node Class
class Node{
 
    // Constructor to initialize the node object
    constructor(val){
        this.data = val
        this.next = null
        this.prev = null
        this.top = null
        this.bottom = null
    }
}
 
// Linked List class
class LinkedList{
 
    // Constructor to initialize head
    constructor(){
        this.head = null
    }
 
    // function to form square
    // linked list of matrix.
    Quad(grid, n, m){
 
        // initialising A[0][0] as head.
        this.head = new Node(grid[0][0])
 
        // head is assigned to head.
        let temp = this.head
 
        // i is row index, j is column index
        let i = 0
        let j = 1
 
        // loop till temp.top become equal to head.
        while(temp.top != this.head){
            // as we iterating over boundary
            // of matrix so we will iterate
            // over first(0) and last(n-1) row
            // and first(0) and last(m-1) column.
 
            // iterating over first i.e 0th row
            // and connecting node.
            if(j < m && i == 0){
                temp.next = new Node(grid[i][j])
                temp = temp.next
                j += 1
            }
 
            // iterating over last i.e (m-1)th
            // column and connecting Node.
            else if (j == m && i < n - 1){
                i = i + 1
                temp.bottom = new Node(grid[i][j - 1])
                temp = temp.bottom
            }
 
            // iterating over last i.e (n-1)th row
            // and connecting Node.
            else if (i == n - 1 && j <= m && j >= 1){
                if (j == m) j = j - 1
                j = j - 1
                temp.prev = new Node(grid[i][j])
                temp = temp.prev
            }
 
            // iterating over first i.e 0th column
            // and connecting Node.
            else if (i <= n - 1 && j == 0){
                i = i - 1
                temp.top = new Node(grid[i][j])
                temp = temp.top
                if(i == 1)
                    temp.top = this.head
            }
        }
    }
 
    // function to print Linked list.
    printList(root){
         
        let temp = root
         
        // printing head of linked list
        document.write(temp.data + " ")
         
        // loop till temp.top
        // become equal to head
        while(temp.top != root){
           
          // printing the node
            if(temp.next){
               document.write(temp.next.data + " ")
                temp = temp.next
            }
            if(temp.prev){
               document.write(temp.prev.data + " ")
                temp = temp.prev
            }
            if(temp.bottom){
               document.write(temp.bottom.data + " ")
                temp = temp.bottom
            }
            if(temp.top){
               document.write(temp.top.data + " ")
                temp = temp.top
            }
        }
    }
}
 
// Driver Code
let grid = [[13, 42, 93, 88],   
        [26, 38, 66, 42],
        [75, 63, 78, 12]]
 
// n is number of rows
let n = grid.length
 
// m is number of column
let m = grid[0].length
 
// creation of object
let l = new LinkedList()
 
// Call Quad method to create Linked List.
l.Quad(grid, n, m)
 
// Call printList method to print list.
l.printList(l.head)
 
// This code is contributed by gfgking.
</script>
Producción

13 42 93 88 42 12 78 63 75 26 

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

Publicación traducida automáticamente

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