# APCS實作題2017年3月第3題：數字龍捲風

> 第1版：2023年2月17日
> 第2版：2023年6月13日，加上 C++ 程式碼
> 第3版：2023年10月19日，將 Python 程式碼改成較精簡的版本
> 作者：王一哲
> 題目來源：[106年3月4日實作題第3題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1060304APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c292)

<br />

## 題目

### 問題描述

給定一個 $N \times N$ 的二維陣列，其中 $N$ 是奇數，我們可以從正中間的位置開始，以順時針旋轉的方式走訪每個陣列元素恰好一次。對於給定的陣列內容與起始方向，請輸出走訪順序之內容。下面的例子顯示了 $N=5$ 且第一步往左的走訪順序：

<img height="50%" width="50%" src="https://i.imgur.com/CPXwwBc.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

依此順序輸出陣列內容則可以得到「9123857324243421496834621」。

類似地，如果是第一步向上，則走訪順序如下：

<img height="50%" width="50%" src="https://i.imgur.com/5DghH4H.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

依此順序輸出陣列內容則可以得到「9385732124214968346214243」。
<br />

### 輸入格式

輸入第一行是整數 $N$，$N$ 為奇數且不小於 3。第二行是一個 0 ~ 3 的整數代表起始方向，其中 0 代表左、1 代表上、2 代表右、3 代表下。第三行開始 $N$ 行是陣列內容，順序是由上而下，由左至右，陣列的內容為 0 ~ 9 的整數，同一行數字中間以一個空白間隔。
<br />

### 輸出格式

請輸出走訪順序的陣列內容，該答案會是一連串的數字，數字之間**不要輸出空白**，結尾有換行符號。
<br />

### 範例一：輸入

5
0
3 4 2 1 4
4 2 3 8 9
2 1 9 5 6
4 2 3 7 8
1 2 6 4 3

### 範例一：正確輸出

9123857324243421496834621

<br />

### 範例二：輸入

3
1
4 1 2
3 0 5
6 7 8

### 範例二：正確輸出

012587634

<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。其中：
- 第 1 子題組 20 分，$3 \leq N \leq 5$，且起始方向均為向左。
- 第 2 子題組 80 分，$3 \leq N \leq 49$，起始方向無限定。

<br />

### 提示

本題有多種處理方式，其中之一是觀察每次轉向與走的步數。例如，起始方向是向左時，前幾步的走法是：左 1、上 1、右 2、下 2、左 3、上 3、……一直到出界為止。

<br />

## Python 程式碼

N = int(input())  # 讀取矩陣的列數、欄數 N
d = int(input())  # 讀取起始方向
data = []  # 儲存矩陣的二維串列
for _ in range(N):  # 讀取矩陣內容
    data.append(list(map(int, input().split())))

directions = ((0, -1), (-1, 0), (0, 1), (1, 0))
direction = directions[d]

def changeDir(dir1):
    if dir1 == (0, -1): return directions[1]
    elif dir1 == (-1, 0): return directions[2]
    elif dir1 == (0, 1): return directions[3]
    else: return directions[0]

x = y = int((N-1)/2)
print(data[x][y], end="")
count = 1
step = 1
while count < N*N:
    for _ in range(step):
        count += 1
        if count <= N*N:
            x += direction[0]
            y += direction[1]
            if count == N*N: print(data[x][y])
            else: print(data[x][y], end="")
        else: break
    direction = changeDir(direction)
    for _ in range(step):
        count += 1
        if count <= N*N:
            x += direction[0]
            y += direction[1]
            print(data[x][y], end="")
        else: break        
    direction = changeDir(direction)
    step += 1

<br />

1. 第1 ~ 5行：從標準輸入讀取資料，矩陣的維度儲存到N，起始方向儲存到d，矩陣內容儲存到 data。
2. 第7、8行：用 tuple 格式的 directons 儲存4個方向，再依照d的值取出對應的方向儲存到 direction。
3. 第10 ~ 14行：自訂函式 changeDir，由原來的方向決定改變後的方向，方向依序為**左、上、右、下**。
4. 第16、17行：計算正中央的元素位置索引值，再印出此元素值。
5. 第20 ~ 38行：在印出第 N² 個元素之前，繼續執行 while 迴圈。由於沿著某個方向移動的步數 step 依序為1、1、2、2、3、3、……，在 while 迴圈之中有兩個 for 迴圈，當一個 for 迴圈執行完畢時用自訂函式 changeDir 改變前進方向，當兩個 for 迴圈都執行完畢時將移動步數 step 加1。最後一個印出的元素一定是在第1個 for 迴圈裡面，所以第33行印出最後一個元素時要換行。
6. 於 ZeroJudge 測試結果，第12筆測資費時最久，約 24 ms，使用記憶體 3.8 MB，通過測試。

<br /><br />

## C++ 程式碼

#include <iostream>
using namespace std;

int changeDir(int);   // 改變方向用的自訂函式
int dirs[][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};   // 儲存方向的二維陣列

int main(int argc, char* argv[]) {
    // 由標準輸入讀取矩陣維度 N、起始方向 D、矩陣資料 data
    int N, D;
    cin >> N >> D;
    int data[N][N];
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> data[i][j];
        }
    }

    // 起始方向
    int* dir = dirs[D];
    
    // 計算矩陣中央的位置並印出元素
    int x = (N-1)/2;
    int y = x;
    cout << data[x][y];
    
    // 已印出元素的次數 count、移動格數 step
    int count = 1, step = 1;
    
    // 順時鐘方向旋轉印出元素值
    while(count < N*N) {
        for(int i=0; i<step; i++) {   // 往一個方向移動 step 格並印出元素
            count++;
            if (count <= N*N) {
                x += dir[0];
                y += dir[1];
                if (count == N*N) {   // 印出最後一個元素時加上換行
                    cout << data[x][y] << endl;
                } else {              // 不是最後一個元素
                    cout << data[x][y];
                }
            } else {
                break;    // 超出邊界終止迴圈
            }
        }
        D = changeDir(D); // 改變方向
        dir = dirs[D];
        for(int i=0; i<step; i++) {   // 往一個方向移動 step 格並印出元素
            count++;
            if (count <= N*N) {       // 不會遇到最後一個元素
                x += dir[0];
                y += dir[1];
                cout << data[x][y];
            }
        }
        D = changeDir(D); // 改變方向
        dir = dirs[D];
        step++;           // 增加移動格數
    }
    return 0;
}

// 改變方向用的自訂函式
int changeDir(int d) {
    if (d == 0) return 1;
    else if (d == 1) return 2;
    else if (d == 2) return 3;
    else return 0;
}

<br />

1. 第4、63 ~ 68行：改變方向用的自訂函式 changeDir，由原來的方向決定改變後的方向，方向依序為**左、上、右、下**。。
2. 第5行：用2維陣列 dirs 儲存4個方向。
3. 第9 ~ 16行：由標準輸入讀取矩陣維度 N、起始方向 D、矩陣資料 data。
4. 第19行：定義方向 dir。
5. 第22 ~ 24行：計算矩陣中央的位置並印出元素。
7. 第30 ~ 58行：在印出第 N² 個元素之前，繼續執行 while 迴圈。由於沿著某個方向移動的步數 step 依序為1、1、2、2、3、3、……，在 while 迴圈之中有兩個 for 迴圈，當一個 for 迴圈執行完畢時用自訂函式 changeDir 及 dir = dirs[D] 改變前進方向，當兩個 for 迴圈都執行完畢時將移動步數 step 加1。最後一個印出的元素一定是在第1個 for 迴圈裡面，所以第37行印出最後一個元素時要換行。
8. 於 ZeroJudge 測試結果，花費時間為 3 ms，使用記憶體 348 kB，通過測試。
9. 由於讀取元素的方向一定是順時鐘方向，表示方向的變數 D 數值變化時依序為 0、1、2、3，可以不需要定義 changeDir，第45、55行改成

	D = (D+1)%4;

於 ZeroJudge 測試結果，花費時間為 3 ms，使用記憶體 332 kB，通過測試。
<br /><br />

---

###### tags:`APCS`、`C++`、`Python`