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 26Explicació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>
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