Dada una array de array bidimensional de n filas y n columnas. Imprima esta array en ZIG-ZAG comenzando desde la columna n-1 como se muestra en la figura a continuación.
Ejemplos:
Input: mat[][] = 1 2 3 4 5 6 7 8 9 Output: 3 2 6 9 5 1 4 8 7 Input: mat[][] = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 4 3 8 12 7 2 1 6 11 16 15 10 5 9 14 13
Algoritmo:
- Comience a atravesar desde la celda superior derecha que pertenece a la fila 0 y la columna n-1.
- El primer movimiento siempre será hacia la dirección IZQUIERDA (OESTE) .
- Hacemos un movimiento horizontal/vertical en caso de que el movimiento sea impar.
- Si el último movimiento fue en dirección NOROESTE , muévase hacia la IZQUIERDA si no hay una pared, muévase hacia la IZQUIERDA , muévase hacia ABAJO si hay una pared a la IZQUIERDA .
- Si el último movimiento fue en dirección SURESTE , muévase hacia ABAJO si no hay un muro HACIA ABAJO , muévase hacia la IZQUIERDA si hay un muro HACIA ABAJO .
- Hacemos un movimiento diagonal en caso de que el movimiento sea par.
- Elegimos movernos hacia las direcciones SURESTE y NOROESTE alternativamente comenzando con el movimiento SURESTE .
- En un solo movimiento diagonal seguimos atravesando múltiples celdas en la misma dirección hasta llegar a cualquiera de las paredes de la array. Pseudocódigo:
if ((move_cnt >> 1) & 1) { // move south east } else { // move north west }
Variables utilizadas
- mat : array NxN dada
- cur_x : Número de fila actual
- cur_y : Número de columna actual
- prev_move : se utiliza para realizar un seguimiento del movimiento anterior
- move_cnt : se utiliza para realizar un seguimiento de la cantidad de movimientos realizados
- cell_cnt : se utiliza para realizar un seguimiento del número de celdas atravesadas
Los códigos a continuación son la implementación del algoritmo anterior.
C++
// C++ program for traversing a matrix from column n-1
#include <bits/stdc++.h>
using namespace std;
// Function used for traversing over the given matrix
void traverseMatrix(vector<vector<int> > mat, int n)
{
// Initial cell coordinates
int cur_x = 0, cur_y = n - 1;
// Variable used for keeping track of last move
string prev_move = "";
// Variable used for keeping count
// of cells traversed till next move
int move_cnt = 1;
int cell_cnt = 1;
printf("%d ", mat[cur_x][cur_y]);
while (cell_cnt < n * n) {
// odd numbered move [SINGLE VERTICAL/HORIZONTAL]
if (move_cnt & 1) {
// last move was made in north east direction
if (prev_move == "NORTH_WEST" or prev_move == "") {
// move left
if (cur_y != 0) {
--cur_y;
prev_move = "LEFT";
}
// move down
else {
++cur_x;
prev_move = "DOWN";
}
}
// last move was made in south east direction
else {
// move down
if (cur_x != n - 1) {
++cur_x;
prev_move = "DOWN";
}
// move left
else {
--cur_y;
prev_move = "LEFT";
}
}
printf("%d ", mat[cur_x][cur_y]);
++cell_cnt;
}
// even numbered move/s [DIAGONAL/S]
else {
if ((move_cnt >> 1) & 1) {
// move south east
while (cur_x < n - 1 and cur_y < n - 1) {
++cur_x;
++cur_y;
prev_move = "SOUTH_EAST";
printf("%d ", mat[cur_x][cur_y]);
++cell_cnt;
}
}
else {
// move north west
while (cur_x > 0 and cur_y > 0) {
--cur_x;
--cur_y;
prev_move = "NORTH_WEST";
printf("%d ", mat[cur_x][cur_y]);
++cell_cnt;
}
}
}
++move_cnt;
}
}
// Driver function
int main()
{
// number of rows and columns
int n = 5;
// 5x5 matrix
vector<vector<int> > mat{
{ 1, 2, 3, 4, 5 },
{ 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 },
{ 16, 17, 18, 19, 20 },
{ 21, 22, 23, 24, 25 }
};
traverseMatrix(mat, n);
return 0;
}
Java
// Java program for traversing a matrix from column n-1
class GFG {
// Function used for traversing over the given matrix
static void traverseMatrix(int[][] mat, int n)
{
// Initial cell coordinates
int cur_x = 0, cur_y = n - 1;
// Variable used for keeping track of last move
String prev_move = "";
// Variable used for keeping count
// of cells traversed till next move
int move_cnt = 1;
int cell_cnt = 1;
System.out.print(Integer.toString(
mat[cur_x][cur_y])
+ " ");
while (cell_cnt < n * n) {
// odd numbered move
// [SINGLE VERTICAL/HORIZONTAL]
if (move_cnt % 2 == 1) {
// last move was made in north east direction
if (prev_move == "NORTH_WEST" || prev_move == "") {
// move left
if (cur_y != 0) {
--cur_y;
prev_move = "LEFT";
}
// move down
else {
++cur_x;
prev_move = "DOWN";
}
}
// last move was made in south east direction
else {
// move down
if (cur_x != n - 1) {
++cur_x;
prev_move = "DOWN";
}
// move left
else {
--cur_y;
prev_move = "LEFT";
}
}
System.out.print(Integer.toString(
mat[cur_x][cur_y])
+ " ");
++cell_cnt;
}
// even numbered move/s [DIAGONAL/S]
else {
if ((move_cnt >> 1) % 2 == 1) {
// move south east
while (cur_x < n - 1 && cur_y < n - 1) {
++cur_x;
++cur_y;
prev_move = "SOUTH_EAST";
System.out.print(
Integer.toString(
mat[cur_x][cur_y])
+ " ");
++cell_cnt;
}
}
else {
// move north west
while (cur_x > 0 && cur_y > 0) {
--cur_x;
--cur_y;
prev_move = "NORTH_WEST";
System.out.print(
Integer.toString(
mat[cur_x][cur_y])
+ " ");
++cell_cnt;
}
}
}
++move_cnt;
}
}
// Driver function
public static void main(String[] args)
{
// number of rows and columns
int n = 5;
// 5x5 matrix
int[][] mat = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 },
{ 16, 17, 18, 19, 20 },
{ 21, 22, 23, 24, 25 }
};
traverseMatrix(mat, n);
System.exit(0);
}
}
Python
# Python program for traversing a matrix from column n-1 import sys; # Function used for traversing over the given matrix def traverseMatrix(mat, n): # Initial cell coordinates cur_x = 0; cur_y = n - 1 # Variable used for keeping track of last move prev_move = "" # Variable used for keeping count # of cells traversed till next move move_cnt = 1 cell_cnt = 1 print(mat[cur_x][cur_y], end = ' ') while cell_cnt < n * n: # odd numbered move [SINGLE VERTICAL / HORIZONTAL] if move_cnt & 1: # last move was made in north east direction if prev_move == "NORTH_WEST" or prev_move == "" : # move left if cur_y != 0: cur_y -= 1 prev_move = "LEFT" # move down else : cur_x += 1 prev_move = "DOWN" # last move was made in south east direction else : # move down if(cur_x != n-1): cur_x += 1 prev_move = "DOWN" # move left else : cur_y -= 1 prev_move = "LEFT" print(mat[cur_x][cur_y], end = ' ') cell_cnt += 1 # even numbered move / s [DIAGONAL / S] else : if (move_cnt >> 1) & 1: # move south east while cur_x < n - 1 and cur_y < n - 1: cur_x += 1; cur_y += 1 prev_move = "SOUTH_EAST" print(mat[cur_x][cur_y], end = ' ') cell_cnt += 1 else : # move north west while cur_x > 0 and cur_y > 0: cur_x -= 1 ; cur_y -= 1 prev_move = "NORTH_WEST"; print(mat[cur_x][cur_y], end = ' ') cell_cnt += 1 move_cnt += 1 # Driver function if __name__ == '__main__': # number of rows and columns n = 5 # 5x5 matrix mat =[ [1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25] ] traverseMatrix(mat, n)
C#
// CSHARP program for traversing a matrix from column n-1
using System;
using System.Linq;
class GFG {
// Function used for traversing over the given matrix
static void traverseMatrix(int[, ] mat, int n)
{
// Initial cell coordinates
int cur_x = 0, cur_y = n - 1;
// Variable used for keeping track of last move
string prev_move = "";
// Variable used for keeping count
// of cells traversed till next move
int move_cnt = 1;
int cell_cnt = 1;
Console.Write(mat[cur_x, cur_y].ToString() + " ");
while (cell_cnt < n * n) {
// odd numbered move [SINGLE VERTICAL/HORIZONTAL]
if (move_cnt % 2 == 1) {
// last move was made in north east direction
if (prev_move == "NORTH_WEST" || prev_move == "") {
// move left
if (cur_y != 0) {
--cur_y;
prev_move = "LEFT";
}
// move down
else {
++cur_x;
prev_move = "DOWN";
}
}
// last move was made in south east direction
else {
// move down
if (cur_x != n - 1) {
++cur_x;
prev_move = "DOWN";
}
// move left
else {
--cur_y;
prev_move = "LEFT";
}
}
Console.Write(
mat[cur_x, cur_y].ToString() + " ");
++cell_cnt;
}
// even numbered move/s [DIAGONAL/S]
else {
if ((move_cnt >> 1) % 2 == 1) {
// Console.WriteLine("[...]");
// move south east
while (cur_x < n - 1 && cur_y < n - 1) {
++cur_x;
++cur_y;
prev_move = "SOUTH_EAST";
Console.Write(
mat[cur_x, cur_y].ToString()
+ " ");
++cell_cnt;
}
}
else {
// move north west
while (cur_x > 0 && cur_y > 0) {
--cur_x;
--cur_y;
prev_move = "NORTH_WEST";
Console.Write(
mat[cur_x, cur_y].ToString()
+ " ");
++cell_cnt;
}
}
}
++move_cnt;
}
}
// Driver function
public static void Main()
{
// number of rows and columns
int n = 5;
// 5x5 matrix
int[, ] mat = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 },
{ 16, 17, 18, 19, 20 },
{ 21, 22, 23, 24, 25 }
};
traverseMatrix(mat, n);
}
}
PHP
<?php
// PHP program for traversing a matrix from column n-1
// Function used for traversing over the given matrix
function traverseMatrix($mat, $n){
# Initial cell coordinates
$cur_x = 0; $cur_y = $n - 1;
# Variable used for keeping track of last move
$prev_move = "";
# Variable used for keeping count
# of cells traversed till next move
$move_cnt = 1;
$cell_cnt = 1;
print($mat[$cur_x][$cur_y]." ");
while ($cell_cnt < $n * $n) {
# odd numbered move [SINGLE VERTICAL/HORIZONTAL]
if ($move_cnt & 1) {
# last move was made in north east direction
if ($prev_move == "NORTH_WEST" or
$prev_move == "") {
# move left
if ($cur_y != 0){
$cur_y -= 1;
$prev_move = "LEFT";
}
# move down
else {
$cur_x += 1;
$prev_move = "DOWN";
}
}
# last move was made in south east direction
else {
# move down
if($cur_x != $n - 1){
$cur_x += 1;
$prev_move = "DOWN";
}
# move left
else {
$cur_y -= 1;
$prev_move = "LEFT";
}
}
print($mat[$cur_x][$cur_y]." ");
$cell_cnt += 1;
}
# even numbered move/s [DIAGONAL/S]
else {
if (($move_cnt >> 1) & 1) {
# move south east
while ($cur_x < $n - 1 and $cur_y < $n - 1) {
$cur_x += 1; $cur_y += 1;
$prev_move = "SOUTH_EAST";
print($mat[$cur_x][$cur_y]." ");
$cell_cnt += 1;
}
}
else {
# move north west
while($cur_x > 0 and $cur_y > 0) {
$cur_x -=1 ; $cur_y -= 1;
$prev_move = "NORTH_WEST";
print($mat[$cur_x][$cur_y]." ");
$cell_cnt += 1;
}
}
}
$move_cnt += 1;
}
}
// Driver function
# number of rows and columns
$n = 5;
# 5x5 matrix
$mat = array(
array(1, 2, 3, 4, 5),
array(6, 7, 8, 9, 10),
array(11, 12, 13, 14, 15),
array(16, 17, 18, 19, 20),
array(21, 22, 23, 24, 25)
);
traverseMatrix($mat, $n);
?>
Producción:
5 4 10 15 9 3 2 8 14 20 25 19 13 7 1 6 12 18 24 23 17 11 16 22 21
Complejidad de tiempo : O(N^2)
Complejidad de espacio : O(1)
Publicación traducida automáticamente
Artículo escrito por Harshit Saini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA