Как построить спиральную квадратную матрицу с помощью рекурсии?
Я хотел построить спиральную квадратную матрицу, используя рекурсию. Я могу построить спиральную квадратную матрицу, используя итерационный метод, как показано ниже:
void main()
{
int initial_direction = UP , n = MAX , p = 1 ; /* intial_direction
is set to UP because we need to start moving right */
int r ,c , a[MAX][MAX];
int row_right = 0 , column_down = n-1 , row_left = n-1 , column_up = 0 ;
clrscr ();
//Set all elements of the matrix to 0
for(r = 0 ; r < MAX ; r++)
{
for(c = 0 ; c < MAX ; c++)
a[r][c] = 0 ;
}
//Generate elements of the spiral matrix
while(p != n*n+1)
{
if(initial_direction == UP)
{
//Move RIGHT
r = row_right++ ;
for(c = 0 ; c < n ; c++)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = RIGHT ;
}
else if(initial_direction == RIGHT)
{
//Move down
c = column_down-- ;
for(r = 0 ; r < n ; r++)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = DOWN ;
}
else if(initial_direction == DOWN)
{
//Move left
r = row_left-- ;
for(c = n-1 ; c >= 0 ; c--)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = LEFT ;
}
else if(initial_direction == LEFT)
{
//Move up
c = column_up++;
for(r = n-1 ; r >= 0 ; r--)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = UP ;
}
}
//Print the matrix
printf("\n\n");
for(r = 0 ; r < MAX ; r++)
{
for(c = 0 ; c < MAX ; c++)
printf("%4d ",a[r][c]);
printf("\n");
}
}
Я хотел создать ту же матрицу, используя рекурсию: вот код, который я использовал:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool s[5][5] = {0};
int counter;
typedef enum {
right = 0,
down,
left,
up
}c_flag;
c_flag flag;
int last;
int build_matrix(int a[5][5],int i,int j, c_flag flag)
{
int ret;
if (i < 0 || i>=5 || j < 0 || j >= 5)
{
if (last == right)
{
flag = down;
last = flag;
}
if (last == down)
{
flag = left;
last = flag;
}
if (last == left)
{
flag = up;
last = flag;
}
if (last == up)
{
flag = left;
last = flag;
}
return false;
}
if (s[i][j] == true)
{
if (last == right)
{
flag = down;
last = flag;
}
if (last == down)
{
flag = left;
last = flag;
}
if (last == left)
{
flag = up;
last = flag;
}
if (last == up)
{
flag = left;
last = flag;
}
return false;
}
if(s[i][j] == false)
{
s[i][j] = true;
a[i][j] = ++ counter;
}
if (flag == right)
{
ret = build_matrix(a,i,j+1,right);
//if (!ret)
// return false;
}
flag = down;
last = flag;
if (flag == down)
{
ret =build_matrix(a,i+1,j,down);
//if (!ret)
// return false;
}
flag = left;
last = flag;
if (flag == left)
{
ret = build_matrix(a,i,j-1,left);
//if (!ret)
// return false;
}
flag = up;
last = flag;
if (flag == up)
{
ret = build_matrix (a,i-1,j,up);
//if (!ret)
// return false;
}
flag = right;
last = flag;
return false;
}
int main()
{
int i, j, n = 5;
int k, ret;
//printf("Enter N to construct square matrix \n");
//scanf("%d",&n);
int a[5][5] = {0};
k = n/2 + n%2;
for (i = 0; i < k; i++)
{
ret = build_matrix(a,i,i,right);
}
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
printf("%d",a[i][j]);
printf("\n");
}
return 0;
}
Я выхожу наверх как:
1 2 3 4 5
16 19 22 25 6
15 18 21 24 7
14 17 20 23 8
13 12 11 10 9
вместо
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Проблема в том, что флажок установлен неправильно, я не знаю, внутри какого флага вызова рекурсии возникают помехи. Пожалуйста, помогите реализовать рекурсию.