原题来源

LeetCode 54.螺旋矩阵

题面解释:

在本题中，我们需要处理一个 ( N \times N ) 的矩阵，每个元素为正整数，且所有正整数从 ( 1 ) 到 ( N^2 ) 恰好出现一次。给定该矩阵的顺时针遍历的结果，要求输出对应的逆时针遍历结果。输入格式为第一行包含一个整数 ( N )，表示矩阵的大小；第二行输入 ( N^2 ) 个整数，表示顺时针链表中每个元素的值。输出格式为 ( N^2 ) 个整数，表示逆时针链表的元素，以空格分隔.

模拟

对于一个大小为n的矩阵，利用一个vis数组先把周围标记墙，从(1,1)开始顺时针(右下左上(循环))模拟走，走过的位置也标记为墙体，碰到墙则进行下一个方向例如(前面一格是墙则反向顺时针旋转90度)，一定能走完n*n的矩阵。还原矩阵，同理按逆时针模拟输出即可$\\$ 整体时间复杂度o(n * n)

题解

在本题中，我们需要处理一个 ( N \times N ) 的矩阵，其中的每个元素都是正整数，且所有的正整数从 ( 1 ) 到 ( N^2 ) 恰好出现一次。我们首先根据给定的顺时针链表生成一个矩阵，然后输出该矩阵的逆时针遍历结果。

思路

1. 初始化访问标记：首先我们定义一个 visited 数组，用来标记矩阵的访问状态。矩阵的边界视为墙体（已访问），内部位置初始为未访问。

2. 顺时针填充矩阵：

   • 从矩阵的左上角 (1,1) 开始，按顺时针方向（右、下、左、上）进行填充。
   • 如果当前方向可以继续前进（即下一个位置未被访问），则继续向该方向前进。
   • 如果碰到墙（已访问），则顺时针旋转90度，尝试下一个方向。

3. 逆时针输出矩阵：

   • 从填充后的矩阵的左上角开始，按逆时针方向（下、右、上、左）进行遍历输出。
   • 同样地，判断下一个位置是否已访问，并适时改变方向。

4. 时间复杂度：整个过程的时间复杂度为 ( O(N^2) )，因为每个位置都会被访问一次。

代码如下

cpp

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

#define MAX_N 105

int n; // 矩阵的阶数
int seq[MAX_N * MAX_N]; // 顺时针链表中的元素值
int mat[MAX_N][MAX_N]; // 矩阵
int visited[MAX_N][MAX_N]; // 访问标记矩阵
int dxClock[4] = {0, 1, 0, -1}; // 顺时针行方向（右、下、左、上）
int dyClock[4] = {1, 0, -1, 0}; // 顺时针列方向
int dxCounter[4] = {1, 0, -1, 0}; // 逆时针行方向（下、右、上、左）
int dyCounter[4] = {0, 1, 0, -1}; // 逆时针列方向

// 初始化访问标记，将矩阵外边界设置为已访问
void initVisitedOuter() {
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= n + 1; j++) {
            visited[i][j] = 1; // 设置矩阵边界为已访问
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            visited[i][j] = 0; // 矩阵内部未访问
        }
    }
}

// 顺时针递归填充矩阵
void fillClockwise(int x, int y, int dir, int idx) {
    mat[x][y] = seq[idx]; // 填入顺时针链表中的值
    visited[x][y] = 1; // 标记当前位置为已访问

    int nx = x + dxClock[dir]; // 计算下一个位置的行坐标
    int ny = y + dyClock[dir]; // 计算下一个位置的列坐标

    if (visited[nx][ny] == 0) { // 如果下一个位置未访问，继续递归
        fillClockwise(nx, ny, dir, idx + 1);
    } else { // 否则换方向
        dir = (dir + 1) % 4; // 顺时针旋转方向
        nx = x + dxClock[dir]; // 更新下一个位置
        ny = y + dyClock[dir];
        if (visited[nx][ny] == 0) {
            fillClockwise(nx, ny, dir, idx + 1);
        }
    }
}

// 逆时针读取矩阵并输出
void outputCounterClockwise(int x, int y, int dir, int idx) {
    if (idx != 1) cout << ' '; // 在输出前加空格，避免开头多余空格
    cout << mat[x][y]; // 输出当前矩阵位置的值
    visited[x][y] = 1; // 标记当前位置为已访问

    int nx = x + dxCounter[dir]; // 计算下一个位置的行坐标
    int ny = y + dyCounter[dir]; // 计算下一个位置的列坐标

    if (visited[nx][ny] == 0) { // 如果下一个位置未访问，继续递归
        outputCounterClockwise(nx, ny, dir, idx + 1);
    } else { // 否则换方向
        dir = (dir + 1) % 4; // 逆时针旋转方向
        nx = x + dxCounter[dir]; // 更新下一个位置
        ny = y + dyCounter[dir];
        if (visited[nx][ny] == 0) {
            outputCounterClockwise(nx, ny, dir, idx + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(0); // 加速输入输出
    cin.tie(0); // 解除 cin 和 cout 的绑定

    cin >> n; // 读取矩阵的大小
    for (int i = 1; i <= n * n; i++) cin >> seq[i]; // 读取顺时针链表

    initVisitedOuter(); // 初始化访问矩阵边界
    fillClockwise(1, 1, 0, 1); // 从 (1, 1) 开始顺时针填充矩阵

    initVisitedOuter(); // 重新初始化访问边界，用于逆时针读取
    outputCounterClockwise(1, 1, 0, 1); // 从 (1, 1) 开始逆时针读取并输出

    return 0; // 程序结束
}

python

import sys
sys.setrecursionlimit(100005)  # 增加递归深度以适应较大的矩阵

MAX_N = 105
n = 0
clockwise_values = [0] * (MAX_N * MAX_N)  # 顺时针链表中的元素值
matrix = [[0] * MAX_N for _ in range(MAX_N)]  # 矩阵
visited = [[0] * MAX_N for _ in range(MAX_N)]  # 访问标记矩阵
dx_clock = [0, 1, 0, -1]  # 顺时针方向行移动
dy_clock = [1, 0, -1, 0]  # 顺时针方向列移动
dx_counter = [1, 0, -1, 0]  # 逆时针方向行移动
dy_counter = [0, 1, 0, -1]  # 逆时针方向列移动

# 初始化访问标记，将矩阵内部设置为未访问
def reset_inner_visited():
    global visited
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            visited[i][j] = 0

# 初始化访问标记，将矩阵外边界设置为已访问
def set_outer_boundary_visited():
    global visited
    for i in range(n + 2):
        for j in range(n + 2):
            visited[i][j] = 1

# 顺时针递归填充矩阵
def fill_clockwise(x, y, direction, idx):
    matrix[x][y] = clockwise_values[idx]
    visited[x][y] = 1

    next_x, next_y = x + dx_clock[direction], y + dy_clock[direction]
    if visited[next_x][next_y] == 0:
        fill_clockwise(next_x, next_y, direction, idx + 1)
    else:
        # 换方向
        direction = (direction + 1) % 4
        next_x, next_y = x + dx_clock[direction], y + dy_clock[direction]
        if visited[next_x][next_y] == 0:
            fill_clockwise(next_x, next_y, direction, idx + 1)

# 逆时针读取矩阵并输出
def output_counter_clockwise(x, y, direction, idx):
    if idx != 1:
        print(' ', end='')
    print(matrix[x][y], end='')

    visited[x][y] = 1
    next_x, next_y = x + dx_counter[direction], y + dy_counter[direction]
    if visited[next_x][next_y] == 0:
        output_counter_clockwise(next_x, next_y, direction, idx + 1)
    else:
        # 换方向
        direction = (direction + 1) % 4
        next_x, next_y = x + dx_counter[direction], y + dy_counter[direction]
        if visited[next_x][next_y] == 0:
            output_counter_clockwise(next_x, next_y, direction, idx + 1)

# 主程序入口
n = int(input())
clockwise_values = [0] + list(map(int, input().split()))  # 顺时针链表
set_outer_boundary_visited()  # 设置矩阵外边界已访问
reset_inner_visited()  # 重置内部为未访问
fill_clockwise(1, 1, 0, 1)  # 顺时针填充矩阵

set_outer_boundary_visited()  # 重新设置矩阵外边界
reset_inner_visited()  # 重置内部为未访问
output_counter_clockwise(1, 1, 0, 1)  # 逆时针输出矩阵

java

import java.util.Scanner;

public class Main {
    static final int MAX_N = 105;
    static int n; // 矩阵的阶数
    static int[] clockwiseValues = new int[MAX_N * MAX_N]; // 顺时针链表中的值
    static int[][] matrix = new int[MAX_N][MAX_N]; // 矩阵
    static int[][] visited = new int[MAX_N][MAX_N]; // 访问标记矩阵
    static int[] dxClock = {0, 1, 0, -1}; // 顺时针方向行移动
    static int[] dyClock = {1, 0, -1, 0}; // 顺时针方向列移动
    static int[] dxCounter = {1, 0, -1, 0}; // 逆时针方向行移动
    static int[] dyCounter = {0, 1, 0, -1}; // 逆时针方向列移动

    // 重置矩阵的内部访问标记为未访问
    static void resetInnerVisited() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                visited[i][j] = 0;
            }
        }
    }

    // 初始化访问标记，将矩阵外边界设置为已访问
    static void setOuterBoundaryVisited() {
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= n + 1; j++) {
                visited[i][j] = 1;
            }
        }
    }

    // 顺时针递归填充矩阵
    static void fillClockwise(int x, int y, int direction, int idx) {
        matrix[x][y] = clockwiseValues[idx];
        visited[x][y] = 1;
        int nextX = x + dxClock[direction];
        int nextY = y + dyClock[direction];
        
        if (visited[nextX][nextY] == 0) {
            fillClockwise(nextX, nextY, direction, idx + 1);
        } else {
            // 改变方向
            direction = (direction + 1) % 4;
            nextX = x + dxClock[direction];
            nextY = y + dyClock[direction];
            if (visited[nextX][nextY] == 0) {
                fillClockwise(nextX, nextY, direction, idx + 1);
            }
        }
    }

    // 逆时针递归输出矩阵
    static void outputCounterClockwise(int x, int y, int direction, int idx) {
        if (idx != 1) System.out.print(' ');
        System.out.print(matrix[x][y]);
        visited[x][y] = 1;
        int nextX = x + dxCounter[direction];
        int nextY = y + dyCounter[direction];
        
        if (visited[nextX][nextY] == 0) {
            outputCounterClockwise(nextX, nextY, direction, idx + 1);
        } else {
            // 改变方向
            direction = (direction + 1) % 4;
            nextX = x + dxCounter[direction];
            nextY = y + dyCounter[direction];
            if (visited[nextX][nextY] == 0) {
                outputCounterClockwise(nextX, nextY, direction, idx + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        
        for (int i = 1; i <= n * n; i++) {
            clockwiseValues[i] = scanner.nextInt();
        }
        
        setOuterBoundaryVisited(); // 初始化矩阵外边界
        resetInnerVisited(); // 重置矩阵内部未访问
        fillClockwise(1, 1, 0, 1); // 顺时针填充矩阵
        
        setOuterBoundaryVisited(); // 重新设置矩阵外边界
        resetInnerVisited(); // 重置矩阵内部未访问
        outputCounterClockwise(1, 1, 0, 1); // 逆时针输出矩阵
    }
}

题目内容

有一个$N×N$的矩阵，其中每个元素都是正整数，且$1$到$N^2$的正整数恰好名出现一次。

可以将这个短阵按照顺时针螺施的方式组成一个链表:从左上角即$(1,1)$号格子出发，沿直线走到右上角即$(1,N)$号格子，再沿直线走到右下角即$(N，N)$号格子，再沿直线走到左下角即$(N,1)$号格子，再沿直线走到左上角下方即$(2,1)$号格子，这就完成了最外面的圈；随后从$(2,1)$号格子走到$(2,2)$号格子，接着完成里面的圈，以此类推，直到结束。

同样地，也可以将其按照逆时针螺旋的方式组成一个链表:从左上角即$(1,1)$号格子出发，沿直线走到左下角即$(N,1)$号格子，再沿直线走到有下角即$(N,N)$号格子，再沿直线走到右上角即$(1,N)$号格子，再沿直线走到左上角右方即$(1,2)$号格子，这就完成了最外面的圈，随后从$(1,2)$号格子走到$(2,2)$号格子，接看完成里面的圈，以此类推，直到结束。

下图给出了$3$ 阶和$4$ 阶矩阵的顺时针链表和逆时针链表的示例。 给定短阵的顺时针链表，求相应的逆时针链表。

输入描述

第一行包含一个整数 $N$，第二行包含 $N^2$个整数，以空格分隔，表示顺时针链表中每个元素的值。

输出描述

含 $N^2$个整数，以空格分隔，表示逆时针链表的每个元素的值。

样例1

输入

3
1 2 3 6 9 8 7 4 5

输出

1 4 7 8 9 6 3 2 5

说明

该矩阵如下:

1 2 3

4 5 6

7 8 9

样例2

输入

4
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

输出

1 5 9 13 14 15 16 12 8 4 3 2 6 10 11 7

说明

该矩阵如下：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16