日期: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;
}
沒有留言:
張貼留言