2025年7月9日 星期三

ZeroJudge 解題筆記:a417. 螺旋矩陣

作者:王一哲
日期:2025年7月9日


ZeroJudge 題目連結:a417. 螺旋矩陣

解題想法


我是先填完矩陣的值再輸出,速度會慢一點。

Python 程式碼


使用時間約為 0.9 s,記憶體約為 21.3 MB,通過測試。
def draw(n, m):
    ### 填格子 ###
    if m == 1:  # 方向順序是右、下、左、上
        dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)
    else:  # 方向順序是下、右、上、左
        dr, dc = (1, 0, -1, 0), (0, 1, 0, -1)
    matrix = [[0]*n for _ in range(n)]  # n*n 矩陣,預設值皆為 0
    r, c, v = 0, 0, 1  # 座標 (r, c),值為 1
    d = 0  # 一開始朝右方或下
    while v < n*n:  # 還沒有填完
        matrix[r][c] = v  # 設定此格的值
        nr, nc = r+dr[d], c+dc[d]  # 要走的格子
        if nr < 0 or nr >= n or nc < 0 or nc >= n or matrix[nr][nc] != 0:  # 出界或已經填過了
            d = (d+1)%4  # 轉向
            nr, nc = r+dr[d], c+dc[d]  # 更新 (nr, nc)
        r, c = nr, nc  # 走到 (nr, nc)
        v += 1  # 值加 1
    matrix[r][c] = v  # 設定最後一格的值
    ### 輸出 ###
    for row in matrix:
        for c, v in enumerate(row):
            print(f"{v:5d}", end="\n" if c == n-1 else "")

T = int(input())
for t in range(T):
    if t > 1: print()
    draw(*map(int, input().split()))


C++ 程式碼


使用時間約為 69 ms,記憶體約為 112 kB,通過測試。
#include <cstdio>
#include <cstring>
using namespace std;

void draw(int n, int m) {
    /* 填格子 */
    int dr[4], dc[4];
    if (m == 1) {  // 方向順序是右、下、左、上
        dr[0] = 0; dr[1] = 1; dr[2] = 0; dr[3] = -1;
        dc[0] = 1; dc[1] = 0; dc[2] = -1; dc[3] = 0;
    } else {  // 方向順序是下、右、上、左
        dr[0] = 1; dr[1] = 0; dr[2] = -1; dr[3] = 0;
        dc[0] = 0; dc[1] = 1; dc[2] = 0; dc[3] = -1;
    }
    int matrix[n][n];  // n*n 矩陣,預設值皆為 0
    memset(matrix, 0, sizeof(matrix));
    int r = 0, c = 0, v = 1, d = 0;  // 座標 (r, c),值為 1,一開始朝右方或下
    while(v < n*n) {  // 還沒有填完
        matrix[r][c] = v;  // 設定此格的值
        int nr = r+dr[d], nc = c+dc[d];  // 要走的格子
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || matrix[nr][nc] != 0) {  // 出界或已經填過了
            d = (d+1)%4;  // 轉向
            nr = r+dr[d]; nc = c+dc[d];  // 更新 (nr, nc)
        }
        r = nr; c = nc;  // 走到 (nr, nc)
        v++;  // 值加 1
    }
    matrix[r][c] = v;  // 設定最後一格的值
    /* 輸出 */
    for(int i=0; i<n; i++) {
        for(int j=0; j<n-1; j++) printf("%5d", matrix[i][j]);
        printf("%5d\n", matrix[i][n-1]);
    }
}

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        if (t > 1) puts("");
        int n, m; scanf("%d %d", &n, &m);
        draw(n, m);
    }
    return 0;
}


沒有留言:

張貼留言