1208 – Spiral Matrix

Program Development Approach

1. Problem Analysis

This program attempts to generate an n×n spiral matrix using a recursive method. The spiral matrix starts from the top-left corner (1,1) and fills numbers in a clockwise direction (right → down → left → up).

2. Algorithm Selection

The program uses a depth-first search (DFS) recursive method:

• Start from the initial point (1,1) and move in the current direction

• If the next position is unavailable (out of bounds or already filled), change direction

• Recursively fill the next position, incrementing the number

• When all positions are filled, the recursion ends

3. Implementation Details

• Use a global variable i to record the current direction index

• Use direction arrays dx and dy to control movement direction

• The recursive function fun handles the filling of each position

• Check the legality of the next position before the recursive call

• Use setw(3) to control output format

Reference Code

#include<bits/stdc++.h>  // Include all standard library headers
using namespace std;
int q[20][20];  // Define a 20x20 2D array to store the spiral matrix
int dx[] = {0, 1, 0, -1};  // Define x direction changes: right, down, left, up
int dy[] = {1, 0, -1, 0};  // Define y direction changes: right, down, left, up
int n, i = 0;  // n is the size of the matrix, i is the direction index (initially 0, indicating right)

// Recursive function to generate the spiral matrix
// Parameters x: current row coordinate
// Parameters y: current column coordinate
// Parameters k: current number to fill
defun(int x, int y, int k){    // Check if the current position is within matrix bounds and not filled
    if(x > 0 && x <= n && y > 0 && y <= n && q[x][y] == 0)    {
        q[x][y] = k;  // Fill the current number k into the matrix at (x,y)
        int tx, ty;  // Define temporary variables to store the next position coordinates
        tx = x + dx[i], ty = y + dy[i];  // Calculate the next position after moving in the current direction
        // Check if the next position is out of bounds or already filled
        if(tx < 1 || tx > n || ty < 1 || ty > n || q[tx][ty])        {
            i = (i + 1) % 4;  // Change direction
            tx = x + dx[i], ty = y + dy[i];  // Recalculate the next position coordinates
        }
        fun(tx, ty, k+1);  // Recursive call to fill the next position, incrementing the number by 1    }}
int main(){    cin >> n;  // Input the size of the matrix n
    fun(1, 1, 1);  // Start recursive filling from position (1,1), starting number is 1
    // Output the spiral matrix    for(int i = 1; i <= n; i++)  // Iterate through each row (from 1 to n)    {
        for(int j = 1; j <= n; j++)  // Iterate through each column (from 1 to n)        {
            cout << setw(3) << q[i][j];  // Output each element, setting width to 3 for alignment        }
            cout << endl;  // New line after each row output    }
    return 8;  // Program ends, returns 8 (note: should typically return 0 to indicate success)}

Program Documentation

Program Functionality

This program attempts to generate an n×n spiral matrix, with numbers starting from 1 filled in a clockwise direction from the outside in.

Variable Explanation

• <span>q[20][20]</span>: 2D array to store the spiral matrix

• <span>dx[]</span> and <span>dy[]</span>: Direction arrays controlling movement in right, down, left, and up

• <span>n</span>: User input for the size of the matrix

• <span>i</span>: Global variable to record the current direction index (0-right, 1-down, 2-left, 3-up)

• Function Parameters:

• <span>x</span>: Current row coordinate

• <span>y</span>: Current column coordinate

• <span>k</span>: Current number to fill

Algorithm Flow

1. User inputs the size of the matrix n

2. Call the recursive function fun starting from position (1,1)

3. In the recursive function:

• Check if the current position is valid (within bounds and not filled)

• Fill the current number

• Calculate the next position

• If the next position is unavailable, change direction

• Recursively call to handle the next position

Output the generated spiral matrix

Expected Output

If the input is 3 and the program is correct, it should output:

text

  1  2  3   8  9  4   7  6  5

Notes

1. The current code has multiple syntax errors and cannot run directly

2. The recursion lacks a clear termination condition, which may lead to stack overflow

3. The global variable i and the loop variable i in the main function have the same name, which may cause conflicts

4. The array index starts from 1 instead of the conventional 0 in C++

5. The program returns 8 instead of 0, which is not conventional

Learning Points

1. Application of recursive algorithms: Using recursion to implement spiral filling

2. Direction control: Using direction arrays to simplify handling of multi-directional movement

3. Boundary checking: Need to check for out-of-bounds or occupied positions when moving

4. Operations on 2D arrays: Filling a 2D array in a specific pattern

5. Output format control: Using setw to set output width