Filling a Spiral Matrix with Offsets, and a Related Zigzag Scan Pattern

Given two integers n and m, the task is to print an n × m matrix filled with the numbers from 1 to n×m in a spiral order that winds inward.

For example, when the input is:

3 3

the required output is:

1 2 3
8 9 4
7 6 5

Input and output format

Input

A single line containing two integers n and m.

Output

Print the matrix that matches the required spiral pattern.

The matrix should occupy n lines, and each line should contain m integers separated by spaces.

Constraints

1 ≤ n, m ≤ 100

How to think about it

A straightforward way to solve this is:

• create an empty 2D array to store the answer;
• walk through the matrix while placing numbers in increasing order;
• before moving to the next cell, check whether that next position is still valid.

One possible method is to write four separate boundary checks with if...else, but a cleaner approach is to use direction offsets.

Using offsets to control movement

Suppose the current position is (x, y). The four neighboring positions are:

• up: (x-1, y)
• right: (x, y+1)
• down: (x+1, y)
• left: (x, y-1)

These movements can be stored in two arrays so they are easy to reuse:

• dx[] for row movement
• dy[] for column movement

In the code below, the direction index starts with dr = 1, which means moving right first. After placing each value:

1. compute the next position;
2. check whether it goes out of bounds, or whether that cell has already been filled;
3. if either condition is true, rotate to the next direction;
4. then continue.

This lets the spiral turn naturally without writing separate logic for every edge.

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn=110;

int a[maxn][maxn];  //定义空的二维数组数组
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};  //初始化方向所对应的偏移量的数组

int main()
{
    int n,m;
    cin>>n>>m;
    int dr=1,x=0,y=0;  //初始化开始方向为右，初始化开始的位置
    for(int i=1;i<=n*m;i++){
        a[x][y]=i;  //存入答案
        int h=x+dx[dr],l=y+dy[dr];  //定义临时变量存放(x,y)的下一个位置的坐标
        if(h<0||l<0||h>=n||l>=m||a[h][l]){  //判断
            dr=(dr+1)%4;
            h=x+dx[dr],l=y+dy[dr];
        }
        x=h,y=l;  //更新(x,y)
    }
    for(int i=0;i<n;i++){  //循环打印输出
        for(int j=0;j<m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Related extension: Zigzag scan of a square matrix

Another matrix traversal problem uses a completely different path: Zigzag Scan.

In image encoding, a square matrix is sometimes read in a zigzag pattern, as shown below:

For the following 4 × 4 matrix:

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

the zigzag scan produces this sequence of length 16:

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

The task is to read an n × n matrix and print its zigzag traversal result.

Input and output format

Input

• The first line contains an integer n, the size of the matrix.
• The next n lines each contain n positive integers separated by spaces.

Output

Print one line containing n×n integers separated by spaces, representing the zigzag scan order.

Constraints

• 1 ≤ n ≤ 500
• each matrix element is a positive integer not greater than 1000

Sample input

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

Sample output

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

Idea behind the zigzag traversal

This traversal is harder than the spiral one because the turning rules near the borders become messy, especially when switching between odd and even diagonals.

A useful trick here is to expand the 2D array conceptually, so that direction changes can be handled in a more uniform way.

By observing the movement pattern, we can define an initial direction dr = 0, then use offset arrays again to describe the next step.

The implementation traverses the enlarged coordinate space, but only prints values when the current position still falls inside the original matrix range.

Code

#include <bits/stdc++.h>
using namespace std;
const int N=505;

int a[2*N][2*N];  //定义时直接扩大

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){  //初始化二维数组
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int dr=0,dx[]={0,1,1,-1},dy[]={1,-1,0,1};  //定义(0,1)的方向dr=0  定义偏移量数组
    printf("%d ",a[0][0]);  //先将(0,0)位置的数输出
    int x=0,y=1;  //初始化位置为(0,1)
    for(int i=0;i<(2*n+1)*n;i++){  //循环遍历扩大后的数组
        if(x<n&&y<n){
            printf("%d ",a[x][y]);  //满足在原始数组范围内输出
        }
        int l=x+dx[dr],r=y+dy[dr];  //临时变量判断下一个要遍历的格子坐标(l,r)
        if(dr==0||dr==2||r<0||l<0||r>=n||l>=n){  //如果dr=0或dr=2或(l,r)出界时改变方向
            dr=(dr+1)%4;
            l=x+dx[dr],r=y+dy[dr];
        }
        x=l,y=r;  //更新(x,y)
    }
    return 0;
}

Both problems rely on the same core technique: describe movement with offset arrays, then decide whether to keep moving in the current direction or turn. Once that pattern is clear, many matrix traversal problems become much easier to implement.