Dada una array 2-D mat[][] , la tarea es imprimirla en forma de espiral.
Ejemplos:
Entrada: mat[][] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Salida : 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Entrada: mat[][] = {
{1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11 , 12},
{13, 14, 15, 16, 17, 18}}
Salida: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
Enfoque: Este problema se puede resolver fácilmente usando el método de dirección. Dado que comenzamos con la dirección Este, siempre giramos a la derecha cada vez que el siguiente índice no es válido (fuera de la array) o se visitó antes. Las direcciones seguidas serán Este -> Sur -> Oeste -> Norte -> … comenzando desde mat[0][0] y finalizando finalmente cuando se hayan recorrido todos los elementos de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define R 5
#define C 5
enum direction { east,
west,
north,
south };
// Function to set the new direction on turning
// right from the current direction
void turnright(enum direction& c_direction)
{
switch (c_direction) {
case east:
c_direction = south;
break;
case west:
c_direction = north;
break;
case north:
c_direction = east;
break;
case south:
c_direction = west;
break;
}
}
// Function to return the next possible cell
// indexes with current direction
pair<int, int> next(int i, int j,
const enum direction& c_direction)
{
switch (c_direction) {
case east:
j++;
break;
case west:
j--;
break;
case north:
i--;
break;
case south:
i++;
break;
}
return pair<int, int>(i, j);
}
// Function that returns true
// if arr[i][j] is a valid index
bool isvalid(const int& i, const int& j)
{
if (i < R && i >= 0 && j >= 0 && j < C)
return true;
return false;
}
// Function that returns true if arr[i][j]
// has already been visited
bool alreadyVisited(int& i, int& j, int& mini, int& minj,
int& maxi, int& maxj)
{
// If inside the current bounds then
// it has not been visited earlier
if (i >= mini && i <= maxi && j >= minj && j <= maxj)
return false;
return true;
}
// Function to update the constraints of the matrix
void ConstraintWalls(int& mini, int& minj, int& maxi,
int& maxj, direction c_direction)
{
// Update the constraints according
// to the direction
switch (c_direction) {
case east:
mini++;
break;
case west:
maxi--;
break;
case north:
minj++;
break;
case south:
maxj--;
break;
}
}
// Function to print the given matrix in the spiral form
void printspiral(int arr[R][C])
{
// To store the count of all the indexes
int count = 0;
// Starting direction is East
enum direction current_direction = east;
// Boundary constraints in the matrix
int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1;
int i = 0, j = 0;
// While there are elements remaining
while (count < (R * C)) {
// Print the current element
// and increment the count
cout << arr[i][j] << " ";
count++;
// Next possible cell if direction remains the same
pair<int, int> p = next(i, j, current_direction);
// If current cell is already visited or is invalid
if (!isvalid(p.first, p.second)
|| alreadyVisited(p.first, p.second, mini, minj, maxi, maxj)) {
// If not visited earlier then only change the constraint
if (!alreadyVisited(i, j, mini, minj, maxi, maxj))
ConstraintWalls(mini, minj, maxi, maxj, current_direction);
// Change the direction
turnright(current_direction);
// Next indexes with new direction
p = next(i, j, current_direction);
}
// Next row and next column
i = p.first;
j = p.second;
}
}
// Driver code
int main()
{
int arr[R][C];
// Fill the matrix
int counter = 1;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
arr[i][j] = counter++;
// Print the spiral form
printspiral(arr);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG {
static int R = 5;
static int C = 5;
// Function to set the new direction on turning
// right from the current direction
public static String turnright(String c_direction)
{
switch (c_direction) {
case "east":
return "south";
case "west":
return "north";
case "north":
return "east";
case "south":
return "west";
}
// returnin null value to avoid the error
return "";
}
// Function to return the next possible cell
// indexes with current direction
public static int[] next(int i, int j,
String c_direction)
{
switch (c_direction) {
case ("east"):
j++;
break;
case "west":
j--;
break;
case "north":
i--;
break;
case "south":
i++;
break;
}
int[] arr = { i, j };
return arr;
}
// Function that returns true
// if arr[i][j] is a valid index
public static boolean isvalid(int i, int j)
{
if (i < R && i >= 0 && j >= 0 && j < C)
return true;
return false;
}
// Function that returns true if arr[i][j]
// has already been visited
public static boolean alreadyVisited(int i, int j,
int mini, int minj,
int maxi, int maxj)
{
// If inside the current bounds then
// it has not been visited earlier
if (i >= mini && i <= maxi && j >= minj
&& j <= maxj)
return false;
return true;
}
// Function to update the constraints of the matrix
public static int[] ConstraintWalls(int mini, int minj,
int maxi, int maxj,
String c_direction)
{
// Update the constraints according
// to the direction
switch (c_direction) {
case "east":
mini++;
break;
case "west":
maxi--;
break;
case "north":
minj++;
break;
case "south":
maxj--;
break;
}
int[] arr = { mini, minj, maxi, maxj };
return arr;
}
// Function to print the given matrix in the spiral form
public static void printspiral(int[][] arr)
{
// To store the count of all the indexes
int count = 0;
// Starting direction is East
String current_direction = "east";
// Boundary constraints in the matrix
int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1;
int i = 0, j = 0;
// While there are elements remaining
while (count < (R * C)) {
// Print the current element
// and increment the count
System.out.print(arr[i][j] + " ");
count += 1;
// Next possible cell if direction remains the
// same
int[] p = next(i, j, current_direction);
// If current cell is already visited or is
// invalid
if (!isvalid(p[0], p[1])
|| alreadyVisited(p[0], p[1], mini, minj,
maxi, maxj)) {
// If not visited earlier then only change
// the constraint
if (!alreadyVisited(i, j, mini, minj, maxi,
maxj)) {
int[] store = ConstraintWalls(
mini, minj, maxi, maxj,
current_direction);
mini = store[0];
minj = store[1];
maxi = store[2];
maxj = store[3];
}
// Change the direction
current_direction
= turnright(current_direction);
// Next indexes with new direction
p = next(i, j, current_direction);
}
// Next row and next column
i = p[0];
j = p[1];
}
}
public static void main(String[] args)
{
int[][] arr = new int[R][C];
// Fill the matrix
int counter = 1;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
arr[i][j] = counter;
counter += 1;
}
// Print the spiral form
printspiral(arr);
}
}
Python3
# Python 3 implementation of the approach R=5 C=5 direction = ['east', 'west', 'north', 'south'] # Function to set the new direction on turning # right from the current direction def turnright(c_direction): if c_direction=='east': return 'south' elif c_direction=='west': return 'north' elif c_direction=='north': return 'east' else: return 'west' # Function to return the next possible cell # indexes with current direction def next(i, j, c_direction): if c_direction=='east': j+=1 elif c_direction=='west': j-=1; elif c_direction=='north': i-=1 else: i+=1 return (i, j) # Function that returns true # if arr[i][j] is a valid index def isvalid(i, j): if (i < R and i >= 0 and j >= 0 and j < C): return True return False # Function that returns true if arr[i][j] # has already been visited def alreadyVisited(i, j, mini, minj, maxi, maxj): # If inside the current bounds then # it has not been visited earlier if (i >= mini and i <= maxi and j >= minj and j <= maxj): return False return True # Function to update the constraints of the matrix def ConstraintWalls(mini, minj, maxi, maxj, c_direction): # Update the constraints according # to the direction if c_direction=='east': mini+=1 elif c_direction=='west': maxi-=1 elif c_direction=='north': minj+=1 else: maxj-=1 return mini, minj, maxi, maxj # Function to print the given matrix in the spiral form def printspiral( arr): # To store the count of all the indexes count = 0 # Starting direction is 'east' current_direction = 'east' # Boundary constraints in the matrix mini = 0; minj = 0; maxi = R - 1; maxj = C - 1 i = 0; j = 0 # While there are elements remaining while (count < (R * C)): # Print the current element # and increment the count print(arr[i][j],end=" ") count+=1 # Next possible cell if direction remains the same p = next(i, j, current_direction) # If current cell is already visited or is invalid if (not isvalid(p[0], p[1]) or alreadyVisited(p[0], p[1], mini, minj, maxi, maxj)): # If not visited earlier then only change the constraint if (not alreadyVisited(i, j, mini, minj, maxi, maxj)): mini, minj, maxi, maxj=ConstraintWalls(mini, minj, maxi, maxj, current_direction) # Change the direction current_direction=turnright(current_direction) # Next indexes with new direction p = next(i, j, current_direction) # Next row and next column i = p[0] j = p[1] # Driver code if __name__ == '__main__': arr=[[0 for j in range(C)]for i in range(R)] # Fill the matrix counter = 1 for i in range(R): for j in range(C): arr[i][j] = counter counter+=1 # Print the spiral form printspiral(arr) print() # This code is contributed by Amartya Ghosh
C#
// C# implementation of the approach
using System;
using System.Text;
public class GFG{
static int R = 5;
static int C = 5;
// Function to set the new direction on turning
// right from the current direction
public static string turnright(string c_direction)
{
switch (c_direction) {
case "east":
return "south";
case "west":
return "north";
case "north":
return "east";
case "south":
return "west";
}
// returnin null value to avoid the error
return "";
}
// Function to return the next possible cell
// indexes with current direction
public static int[] next(int i, int j, string c_direction)
{
switch (c_direction) {
case ("east"):
j++;
break;
case "west":
j--;
break;
case "north":
i--;
break;
case "south":
i++;
break;
}
int[] arr = { i, j };
return arr;
}
// Function that returns true
// if arr[i][j] is a valid index
public static bool isvalid(int i, int j)
{
if (i < R && i >= 0 && j >= 0 && j < C)
return true;
return false;
}
// Function that returns true if arr[i][j]
// has already been visited
public static bool alreadyVisited(int i, int j, int mini, int minj, int maxi, int maxj)
{
// If inside the current bounds then
// it has not been visited earlier
if (i >= mini && i <= maxi && j >= minj && j <= maxj)
return false;
return true;
}
// Function to update the constraints of the matrix
public static int[] ConstraintWalls(int mini, int minj, int maxi, int maxj, string c_direction)
{
// Update the constraints according
// to the direction
switch (c_direction) {
case "east":
mini++;
break;
case "west":
maxi--;
break;
case "north":
minj++;
break;
case "south":
maxj--;
break;
}
int[] arr = { mini, minj, maxi, maxj };
return arr;
}
// Function to print the given matrix in the spiral form
public static void printspiral(int[,] arr)
{
// To store the count of all the indexes
int count = 0;
// Starting direction is East
string current_direction = "east";
// Boundary constraints in the matrix
int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1;
int i = 0, j = 0;
// While there are elements remaining
while (count < (R * C)) {
// Print the current element
// and increment the count
Console.Write(arr[i,j] + " ");
count += 1;
// Next possible cell if direction remains the
// same
int[] p = next(i, j, current_direction);
// If current cell is already visited or is
// invalid
if (!isvalid(p[0], p[1]) || alreadyVisited(p[0], p[1], mini, minj,maxi, maxj)) {
// If not visited earlier then only change
// the constraint
if (!alreadyVisited(i, j, mini, minj, maxi, maxj)) {
int[] store = ConstraintWalls(mini, minj, maxi, maxj,current_direction);
mini = store[0];
minj = store[1];
maxi = store[2];
maxj = store[3];
}
// Change the direction
current_direction = turnright(current_direction);
// Next indexes with new direction
p = next(i, j, current_direction);
}
// Next row and next column
i = p[0];
j = p[1];
}
}
//Driver Code
static public void Main (){
int[,] arr = new int[R,C];
// Fill the matrix
int counter = 1;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
arr[i,j] = counter;
counter += 1;
}
// Print the spiral form
printspiral(arr);
}
}
//This code is contributed by shruti456rawal
Javascript
// Javascript implementation of the approach
var R = 5;
var C = 5;
// Function to set the new direction on turning
// right from the current direction
function turnright(c_direction)
{
switch (c_direction) {
case "east":
return "south";
case "west":
return "north";
case "north":
return "east";
case "south":
return "west";
}
// returnin null value to avoid the error
return "";
}
// Function to return the next possible cell
// indexes with current direction
function next(i, j, c_direction)
{
switch (c_direction) {
case ("east"):
j++;
break;
case "west":
j--;
break;
case "north":
i--;
break;
case "south":
i++;
break;
}
var arr = [i,j];
return arr;
}
// Function that returns true
// if arr[i][j] is a valid index
function isvalid(i, j)
{
if (i < R && i >= 0 && j >= 0 && j < C)
return true;
return false;
}
// Function that returns true if arr[i][j]
// has already been visited
function alreadyVisited(i, j, mini,
minj, maxi, maxj)
{
// If inside the current bounds then
// it has not been visited earlier
if (i >= mini && i <= maxi && j >= minj && j <= maxj)
return false;
return true;
}
// Function to update the constraints of the matrix
function ConstraintWalls(mini, minj,
maxi, maxj, c_direction)
{
// Update the constraints according
// to the direction
switch (c_direction) {
case "east":
mini++;
break;
case "west":
maxi--;
break;
case "north":
minj++;
break;
case "south":
maxj--;
break;
}
var store = [mini,minj,maxi,maxj];
return store;
}
// Function to print the given matrix in the spiral form
function printspiral(arr)
{
// To store the count of all the indexes
var count = 0;
// Starting direction is East
var current_direction = "east";
// Boundary constraints in the matrix
var mini = 0, minj = 0, maxi = R - 1, maxj = C - 1;
var i = 0, j = 0;
// string to store the answer
var ans = "";
// While there are elements remaining
while (count < (R * C))
{
// Print the current element
// and increment the count
ans += arr[i][j] + " ";
count += 1;
// Next possible cell if direction remains the same
var p = next(i, j, current_direction);
// If current cell is already visited or is invalid
if (!isvalid(p[0], p[1])
|| alreadyVisited(p[0], p[1], mini, minj,
maxi, maxj)) {
// If not visited earlier then only change the constraint
if (!alreadyVisited(i, j, mini, minj, maxi, maxj))
{
var store = ConstraintWalls(mini, minj, maxi,
maxj, current_direction);
mini = store[0];
minj = store[1];
maxi = store[2];
maxj = store[3];
}
// Change the direction
current_direction = turnright(current_direction);
// Next indexes with new direction
p = next(i, j, current_direction);
}
// Next row and next column
i = p[0];
j = p[1];
}
console.log(ans);
}
// Fill the matrix
var counter = 1;
var arr = new Array(R);
for (var i = 0; i < R; i++)
{
arr[i] = new Array(C);
for (var j = 0; j < C; j++)
{
arr[i][j] = counter;
counter += 1;
}
}
// Print the spiral form
printspiral(arr);
Producción:
1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13
Complejidad de tiempo: O(R*C)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por priyantanugupta1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA