C语言 经典题目螺旋矩阵 实例详解

问题描述

给定一个正方形的矩阵，要求以从左上角开始，顺时针方向遍历所有元素，按照遍历顺序存储到一个一维数组中。如下图所示，对于输入的矩阵 arr，应输出一个一维数组 res，其中res = {1, 2, 3, 6, 9, 8, 7, 4, 5}。

1   2   3
4   5   6
7   8   9

解题思路

我们可以定义一个方向数组dir，dir数组中的四个元素分别表示上下左右四个方向。通过不断更新当前位置curRow、curCol，以及当前方向currentDir，来实现按照遍历顺序输出各个元素。

具体的实现方式可以参考下面的代码：

void print(int **arr, int n) {
    int *res = (int*)malloc(sizeof(int)*n*n);
    int curRow = 0, curCol = 0, k = 0;
    int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//上右下左
    int currentDir = 1; //当前方向初始为向右
    int visited[n][n];//记录该位置是否已经被访问
    memset(visited, 0, n*n*sizeof(int));//初始所有位置均未访问
    while(k < n*n) {//遍历所有元素
        res[k++] = arr[curRow][curCol];
        visited[curRow][curCol] = 1; //标记当前位置已经访问
        int nextRow = curRow + dir[currentDir][0], nextCol = curCol + dir[currentDir][1];
        if(nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n && !visited[nextRow][nextCol]) {//判断下一个访问位置是否越界或已经访问
            curRow = nextRow; curCol = nextCol;//更新当前位置
        } else {//如果越界或者已经访问，则需要更换方向
            currentDir = (currentDir + 1) % 4;//更换方向
            curRow += dir[currentDir][0]; curCol += dir[currentDir][1];//更新当前位置
        }
    }
    for(int i = 0; i < n*n; i++)
        printf("%d ", res[i]);
    printf("\n");
}

示例说明

针对矩阵：

1   2   3
4   5   6
7   8   9

使用上述代码执行 print(arr, 3) 函数，则会得到输出：1 2 3 6 9 8 7 4 5。

再举一个例子，针对矩阵：

1   2
3   4

使用上述代码执行 print(arr, 2) 函数，则会得到输出: 1 2 4 3。

总之，对于任意输入的正方形矩阵，都能够正确地输出按照遍历顺序存储到一维数组中的元素。