c292 - APCS2017-0304-3數字龍捲風
題目描述
題目給定一個 N x N 的二維陣列，要求從中心點開始，按照螺旋順時針方向走訪陣列中的每個元素，並輸出走訪順序對應的數字。起始方向由輸入指定。
解題思路
本題的核心在於模擬螺旋走訪的過程。可以通過控制當前位置的座標 (x, y) 和方向 (dir) 來實現。每次移動後，輸出當前位置的元素值。
- 初始化：從中心點 (len/2, len/2) 開始，設定起始方向。
- 移動：根據當前方向更新座標。
- 輸出：輸出新座標對應的陣列元素。
- 轉彎：根據步數和方向，判斷是否需要轉彎。轉彎的邏輯是按照層數增加，每層轉彎兩次。
- 重複：重複步驟 2-4，直到走訪完所有元素。
複雜度分析
- 時間複雜度: O(N*N) 因為需要遍歷整個 N x N 的陣列一次。
- 空間複雜度: O(N*N) 因為需要儲存 N x N 的陣列。
程式碼
#include <stdio.h>
#include <stdlib.h>
#define X 0
#define Y 1
int arr[5000][5000];
int move[4][2]={{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
void getxy(int, int);
int main(void) {
int len, dir;
scanf("%d %d", &len, &dir);
for(int i=0;i<len;i++) {
for(int j=0;j<len;j++) {
scanf("%d", &arr[i][j]);
}
}
int nowX=len/2, nowY=nowX;//start in middle
getxy(nowX, nowY);
for(int i=1;i<len;i++) {
for(int k=0;k<2;k++) {
for(int j=0;j<i;j++) {
nowX+=move[dir][X];
nowY+=move[dir][Y];
getxy(nowX, nowY);
}
dir=(dir+1)%4;
}
}
for(int i=1;i<len;i++) {
nowX+=move[dir][X];
nowY+=move[dir][Y];
getxy(nowX, nowY);
}
}
void getxy(int x, int y) {
printf("%d", arr[y][x]);//陣列裡的xy和直角座標系統剛好相反
}