Print 2-D Array in clockwise expanding spiral from center
Let's identify the patterns first ..
Even-Size Square Matrix, Example: 4x4
07 > 08 > 09 > 10
^ v
06 (01)> 02 11
^ v v
05 < 04 < 03 12
v
[16]< 15 < 14 < 13
Starting Point: [2, 2] ~ [SIZE/2, SIZE/2]
Ending Point: [4, 1] ~ [SIZE, 1]
Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
+ 3 for Count = SIZE-1
Odd-Size Square Matrix, Example: 5x5
21 > 22 > 23 > 24 >[25]
^
20 07 > 08 > 09 > 10
^ ^ v
19 06 (01)> 02 11
^ ^ v v
18 05 < 04 < 03 12
^ v
17 < 16 < 15 < 14 < 13
Starting Point: [2, 2] ~ [⌊SIZE/2⌋, ⌊SIZE/2⌋]
Ending Point: [1, 5] ~ [1, SIZE]
Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
+ 3 for Count = SIZE-1
Live Code
void print_spiral (int ** matrix, int size)
{
int x = 0; // current position; x
int y = 0; // current position; y
int d = 0; // current direction; 0=RIGHT, 1=DOWN, 2=LEFT, 3=UP
int c = 0; // counter
int s = 1; // chain size
// starting point
x = ((int)floor(size/2.0))-1;
y = ((int)floor(size/2.0))-1;
for (int k=1; k<=(size-1); k++)
{
for (int j=0; j<(k<(size-1)?2:3); j++)
{
for (int i=0; i<s; i++)
{
std::cout << matrix[x][y] << " ";
c++;
switch (d)
{
case 0: y = y + 1; break;
case 1: x = x + 1; break;
case 2: y = y - 1; break;
case 3: x = x - 1; break;
}
}
d = (d+1)%4;
}
s = s + 1;
}
}
C - spiral traversal of 2D array outwards (starting from center) and clockwise
You can use same implementation and change direction of first step here: Print 2-D Array in clockwise expanding spiral from center
int x = 0; // current position; x
int y = 0; // current position; y
int d = 0; // current direction; 0=RIGHT, 1=DOWN, 2=LEFT, 3=UP
int c = 0; // counter
int s = 1; // chain size
int d
- is current direction; change it to 3
.
Print two-dimensional array in spiral order
The idea is to treat the matrix as a series of layers, top-right layers and bottom-left layers. To print the matrix spirally we can peel layers from these matrix, print the peeled part and recursively call the print on the left over part. The recursion terminates when we don't have any more layers to print.
Input matrix:
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
7 8 9 1
After peeling top-right layer:
1 2 3 4
8
5 6 7 2
9 0 1 6
3 4 5 1
7 8 9
After peeling bottom-left layer from sub-matrix:
6 7
5 0 1
9 4 5
3
7 8 9
After peeling top-right layer from sub-matrix:
6 7
1
0 5
4
After peeling bottom-left layer from sub-matrix:
0
4
Recursion terminates.
C functions:
// function to print the top-right peel of the matrix and
// recursively call the print bottom-left on the submatrix.
void printTopRight(int a[][COL], int x1, int y1, int x2, int y2) {
int i = 0, j = 0;
// print values in the row.
for(i = x1; i<=x2; i++) {
printf("%d ", a[y1][i]);
}
// print values in the column.
for(j = y1 + 1; j <= y2; j++) {
printf("%d ", a[j][x2]);
}
// see if more layers need to be printed.
if(x2-x1 > 0) {
// if yes recursively call the function to
// print the bottom left of the sub matrix.
printBottomLeft(a, x1, y1 + 1, x2-1, y2);
}
}
// function to print the bottom-left peel of the matrix and
// recursively call the print top-right on the submatrix.
void printBottomLeft(int a[][COL], int x1, int y1, int x2, int y2) {
int i = 0, j = 0;
// print the values in the row in reverse order.
for(i = x2; i>=x1; i--) {
printf("%d ", a[y2][i]);
}
// print the values in the col in reverse order.
for(j = y2 - 1; j >= y1; j--) {
printf("%d ", a[j][x1]);
}
// see if more layers need to be printed.
if(x2-x1 > 0) {
// if yes recursively call the function to
// print the top right of the sub matrix.
printTopRight(a, x1+1, y1, x2, y2-1);
}
}
void printSpiral(int arr[][COL]) {
printTopRight(arr,0,0,COL-1,ROW-1);
printf("\n");
}
print 2-D array in spiral order
here is some Java solution:
public static final int X_SIZE = 4;
public static final int Y_SIZE = 4;
public static void main(String[] args) {
int[][] array = new int[X_SIZE][Y_SIZE];
for(int i = 0; i < X_SIZE; i++){
for (int j = 0; j < Y_SIZE; j++){
array[i][j] = i * X_SIZE + (j + 1);
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.out.println("************");
System.out.println("Spiral");
spiralPrint(X_SIZE, Y_SIZE, array);
}
public static void spiralPrint(int xSize, int ySize, int matrix[][]){
int i, k = 0, l = 0;
xSize--; ySize--;
while(k <= xSize && l <= ySize){
for(i = l; i <= ySize; ++i) {
System.out.print(matrix[k][i]+ " ");
}
k++;
for(i = k; i <= xSize; ++i) {
System.out.print(matrix[i][ySize] + " ");
}
ySize--;
for(i = ySize; i >= l; --i) {
System.out.print(matrix[xSize][i] + " ");
}
xSize--;
for(i = xSize; i >= k; --i) {
System.out.print(matrix[i][l] + " ");
}
l++;
}
}
Looping in a spiral
Here's my solution (in Python):
def spiral(X, Y):
x = y = 0
dx = 0
dy = -1
for i in range(max(X, Y)**2):
if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
print (x, y)
# DO STUFF...
if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y):
dx, dy = -dy, dx
x, y = x+dx, y+dy
Related Topics
Enumdisplaydevices VS Wmi Win32_Desktopmonitor, How to Detect Active Monitors
Does Std::Cout Have a Return Value
Overloading Operator<< for a Templated Class
How to Convert from Lpctstr to Std::String
How to Safely Destruct a Qthread
Programmatically Getting System Boot Up Time in C++ (Windows)
Making a Vector of Instances of Different Subclasses
What Happens When a Function That Returns an Object Ends Without a Return Statement
Unique_Ptr and Openssl's Stack_Of(X509)*
How to Remove Straight Lines or Non-Curvical Lines in a Canny Image
Why Do Two Functions Have the Same Address
Cmake: Project Structure with Unit Tests
Memory Alignment:How to Use Alignof/Alignas