Dada una array de orden M*N y un valor K, la tarea es rotar cada anillo de la array en sentido antihorario por K elementos. Si en algún anillo los elementos son menores e iguales a K, entonces no lo gire.
Ejemplos:
Input : k = 3
mat[4][4] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output: 4 8 12 16
3 10 6 15
2 11 7 14
1 5 9 13
Input : k = 2
mat[3][4] = {{1, 2, 3, 4},
{10, 11, 12, 5},
{9, 8, 7, 6}}
Output: 3 4 5 6
2 11 12 7
1 10 9 8
La idea es atravesar la array en forma de espiral . Aquí está el algoritmo para resolver este problema:
- Cree una array auxiliar temp[] de tamaño M*N.
- Comience a atravesar la array en forma de espiral y almacene los elementos del anillo actual en la array temp[]. Mientras almacena los elementos en temperatura, realice un seguimiento de las posiciones inicial y final del anillo actual.
- Por cada anillo que se almacena en temp[], gire ese subarreglo temp[]
- Repita este proceso para cada anillo de array.
- En la última array transversal nuevamente en espiral y copie los elementos de la array temp[] en la array.
A continuación se muestra la implementación en C++ de los pasos anteriores.
CPP
// C++ program to rotate individual rings by k in
// spiral order traversal.
#include<bits/stdc++.h>
#define MAX 100
using namespace std;
// Fills temp array into mat[][] using spiral order
// traversal.
void fillSpiral(int mat[][MAX], int m, int n, int temp[])
{
int i, k = 0, l = 0;
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index */
int tIdx = 0; // Index in temp array
while (k < m && l < n)
{
/* first row from the remaining rows */
for (int i = l; i < n; ++i)
mat[k][i] = temp[tIdx++];
k++;
/* last column from the remaining columns */
for (int i = k; i < m; ++i)
mat[i][n-1] = temp[tIdx++];
n--;
/* last row from the remaining rows */
if (k < m)
{
for (int i = n-1; i >= l; --i)
mat[m-1][i] = temp[tIdx++];
m--;
}
/* first column from the remaining columns */
if (l < n)
{
for (int i = m-1; i >= k; --i)
mat[i][l] = temp[tIdx++];
l++;
}
}
}
// Function to spirally traverse matrix and
// rotate each ring of matrix by K elements
// mat[][] --> matrix of elements
// M --> number of rows
// N --> number of columns
void spiralRotate(int mat[][MAX], int M, int N, int k)
{
// Create a temporary array to store the result
int temp[M*N];
/* s - starting row index
m - ending row index
l - starting column index
n - ending column index; */
int m = M, n = N, s = 0, l = 0;
int *start = temp; // Start position of current ring
int tIdx = 0; // Index in temp
while (s < m && l < n)
{
// Initialize end position of current ring
int *end = start;
// copy the first row from the remaining rows
for (int i = l; i < n; ++i)
{
temp[tIdx++] = mat[s][i];
end++;
}
s++;
// copy the last column from the remaining columns
for (int i = s; i < m; ++i)
{
temp[tIdx++] = mat[i][n-1];
end++;
}
n--;
// copy the last row from the remaining rows
if (s < m)
{
for (int i = n-1; i >= l; --i)
{
temp[tIdx++] = mat[m-1][i];
end++;
}
m--;
}
/* copy the first column from the remaining columns */
if (l < n)
{
for (int i = m-1; i >= s; --i)
{
temp[tIdx++] = mat[i][l];
end++;
}
l++;
}
// if elements in current ring greater than
// k then rotate elements of current ring
if (end-start > k)
{
// Rotate current ring using reversal
// algorithm for rotation
reverse(start, start+k);
reverse(start+k, end);
reverse(start, end);
// Reset start for next ring
start = end;
}
}
// Fill temp array in original matrix.
fillSpiral(mat, M, N, temp);
}
// Driver program to run the case
int main()
{
// Your C++ Code
int M = 4, N = 4, k = 3;
int mat[][MAX]= {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16} };
spiralRotate(mat, M, N, k);
// print modified matrix
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << mat[i][j] << " ";
cout << endl;
}
return 0;
}
4 8 12 16 3 10 6 15 2 11 7 14 1 5 9 13
Complejidad de tiempo: O (M * N) ya que estamos usando bucles anidados para atravesar la array.
Espacio auxiliar: O(M*N) ya que estamos usando espacio adicional para la array.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA