Note: Code snippet loading may take few seconds.Generate a square matrix of size n, such that
- it has elements from 1 to n*2 (or 0 to n*2-1)
- lowest element is at [n,n] (or [n-1,n-1])
- elements are arranged in a spiral order as shown in Figure.
M2 = M3=
| 3 4 | | 5 6 7 |
| 2 1 | | 4 9 8 |
| 3 2 1 |
This is really simple when we consider pattern of filling these elements at an abstract level. Our general approach is to find position for element in order {1, 2, 3, ..., n*n}
We start with rightmost bottom position and put first element there. Then we decide direction to proceed in, which is horizontal in this case. For every next element, we seek a position for it in following way-
We consider adjacent positions of current position in the direction we are in, i.e. here we consider [n,n-1] and [n,n+1] (with [n,n] as our rightmost bottom position. We see if any of this is free. We generalize any position outside matrix dimensions to be non-free and thus next position we have is [n,n-1]. We fill next element in this position and keep going.
At some point, we will find no position free for next element in the direction we are in, which is signal for us to change direction. We switch to vertical direction now and keep going with same logic. This w
ay, we keep moving ahead, find a free slot and change direction if we don't find one.
Note that when we fill in last element, we no longer find free position in either direction and we are done.
Following is the C code.
// generates a spiral square matrix of n*n
// @author Girija
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
int i, j, num;
int pi, pj;
bool pfound;
// setup
int n = atoi(argv[1]);
bool horizontal = true;
int max_num = num*num; // starts at 1
// allocate
int **matrix = (int **) malloc(sizeof(int) * n * n);
// initialize
for(i=0; i<n; i++) {
matrix[i] = (int *) malloc(sizeof(int) * n);
for(j=0; j<n; j++) {
matrix[i][j] = -1;
}
}
pi = pj = n-1;
// generate spiral matrix
num = 1;
while(1) {
// place current number at pi,pj
matrix[pi][pj] = num;
// get position to place next number
pfound = false;
if(horizontal) {
// we are following horizontal direction, check left-right empty slots first
// check if empty slot, reset pj
if(pj-1 >=0 && matrix[pi][pj-1] == -1) {
pj--;
pfound = true;
}
else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
pj++;
pfound = true;
}
if(!pfound) {
// time to change direction
horizontal = false;
// reset pi
if(pi-1 >= 0 && matrix[pi-1][pj] == -1) {
pi--;
pfound = true;
}
else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
pi++;
pfound = true;
}
}
} else {
// we are following vertical direction, check up-down empty slots first
// check if empty slot, reset pi
if(pi-1 >=0 && matrix[pi-1][pj] == -1) {
pi--;
pfound = true;
}
else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
pi++;
pfound = true;
}
if(!pfound) {
// time to change direction
horizontal = true;
// reset pj
if(pj-1 >= 0 && matrix[pi][pj-1] == -1) {
pj--;
pfound = true;
}
else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
pj++;
pfound = true;
}
}
}
// not found? we are done!
if(!pfound)
break;
num++;
}
for(i=0; i<n; i++) {
printf("n");
for(j=0; j<n; j++) {
printf("%dt", matrix[i][j]);
}
}
printf("n");
}
