Editorial for 數字龍捲風 (APCS 2017-03 中級)

簡潔題意

\(N \times N\) 的數字陣列（\(N\) 為奇數），從正中央出發、以順時針旋轉的方式走訪每一格恰好一次，起始方向由輸入指定（\(0\) 左、\(1\) 上、\(2\) 右、\(3\) 下）。依走訪順序把數字不加空白連成一串輸出（\(3 \le N \le 49\)、每格 \(0 \sim 9\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(20\) 分）：\(3 \le N \le 5\)，且起始方向均為左。
  • 子題組 2（\(80\) 分）：無額外限制。

先拿下子題組 1（20 分）：照題目的提示把四段走法寫死

題目自己把走法講完了：起始方向是左時，左 \(1\)、上 \(1\)、右 \(2\)、下 \(2\)、左 \(3\)、上 \(3\)、右 \(4\)、下 \(4\)……每一輪「左、上」走 \(len\) 步、「右、下」走 \(len + 1\) 步，下一輪 \(len\) 再加 \(2\)。子題組 1 保證起始方向就是左，所以四個方向的順序是固定的——直接寫成四段迴圈，每段負責一個方向：

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

int main() {
    int n, dir;
    cin >> n >> dir;                   // 子題組 1 保證 dir = 0（左），但還是要照格式讀掉
    vector<vector<int>> a(n, vector<int>(n));
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++)
            cin >> a[r][c];

    int r = n / 2, c = n / 2;          // 從正中央出發
    int printed = 1;
    cout << a[r][c];
    int len = 1;                       // 這一輪「左、上」各走幾步；「右、下」再多一步
    while (printed < n * n) {
        for (int step = 0; step < len && printed < n * n; step++) {   // 左
            c--;
            cout << a[r][c];
            printed++;
        }
        for (int step = 0; step < len && printed < n * n; step++) {   // 上
            r--;
            cout << a[r][c];
            printed++;
        }
        len++;
        for (int step = 0; step < len && printed < n * n; step++) {   // 右
            c++;
            cout << a[r][c];
            printed++;
        }
        for (int step = 0; step < len && printed < n * n; step++) {   // 下
            r++;
            cout << a[r][c];
            printed++;
        }
        len++;
    }
    cout << '\n';
    return 0;
}

三個地方別踩：

  • 中央那一格要先印——它不屬於任何一段，走法是從它出發，不是走到它。
  • 陣列由上而下、由左至右讀進來，所以「上」是 r--、「左」是 c--（13.1）。
  • 最後一段走不滿：範例 1（\(N = 5\)）走完下 \(4\) 之後只剩 \(4\) 格，「左 \(5\)」走到第 \(4\) 步就得停。每段迴圈裡的 printed < n * n 就是為此而設——印滿 \(N^2\) 個就停，多走一步就出界了。從中央往外繞，在印滿之前永遠不會出界，所以除了這個煞車，什麼邊界判斷都不用。

這份程式交上去，範例 2 和起始方向不是左的測資會 WA——這是正常的，逐筆給分之下子題組 1 的 \(20\) 分穩穩到手。

從 20 分到 100 分：方向表＋右轉一行

起始方向不固定之後，「左、上、右、下」這個輪替得從輸入給的方向開始轉——四段寫死的迴圈就不夠用了。把方向打成表（13.3）：題目的編號 \(0\) 左、\(1\) 上、\(2\) 右、\(3\) 下本身就是順時針，所以「每段走完右轉一次」就是 dir = (dir + 1) % 4；四段迴圈合成一段，步長 \(1, 1, 2, 2, 3, 3, \dots\) 則是「同一個 len 走兩段，再加一」。這正是語法書 13.10 的螺旋走訪：

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

// 題目的方向編號：0 左、1 上、2 右、3 下——本身就是順時針，右轉＝編號 +1
const int dr[4] = {0, -1, 0, 1};
const int dc[4] = {-1, 0, 1, 0};

int main() {
    int n, dir;
    cin >> n >> dir;
    vector<vector<int>> a(n, vector<int>(n));
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++)
            cin >> a[r][c];

    int r = n / 2, c = n / 2;          // 從正中央出發
    int printed = 1;
    cout << a[r][c];
    for (int len = 1; printed < n * n; len++) {           // 步長 1,1,2,2,3,3,…
        for (int twice = 0; twice < 2 && printed < n * n; twice++) {
            for (int step = 0; step < len && printed < n * n; step++) {
                r += dr[dir];  c += dc[dir];
                cout << a[r][c];
                printed++;
            }
            dir = (dir + 1) % 4;                          // 每段走完右轉
        }
    }
    cout << '\n';
    return 0;
}

跟子題版比，換掉的只有兩件事：

  • 四段迴圈變一段：往哪走由 dr[dir]、dc[dir] 決定，走完一段 dir 加一——起始方向是誰都一樣。
  • 步長的節奏交給 twice：外層 len 每加一，中間就用同一個 len 走兩段，正好是 \(1, 1, 2, 2, 3, 3, \dots\)。

printed < n * n 三處都在，理由和子題版一樣：最後一段走不滿，它是唯一的煞車。\(N \le 49\)，總共印 \(2401\) 個字、每格只走一次，速度完全不是問題。

測過再交：範例只從左、上出發過

兩個範例的起始方向是左（範例 1）和上（範例 2），右和下一次都沒出現——方向表抄錯一格、或右轉寫成左轉，只靠範例不一定抓得到。另外兩個範例的最後一段都走不滿，但都沒有直接驗過「總長度就是 \(N^2\)」。用最小的 \(3 \times 3\) 自己造：

輸入 正確輸出 這一筆在測什麼
3 ／ 0 ／ 1 2 3 ／ 4 5 6 ／ 7 8 9 541236987 子題組 1 的最小情況：中央 5 先印、左 4、上 1、右 2 3、下 6 9、最後一段左只剩 8 7
3 ／ 2 ／ 1 2 3 ／ 4 5 6 ／ 7 8 9 569874123 起始方向右（範例沒有）：右 6、下 9、左 8 7、上 4 1、右 2 3
3 ／ 3 ／ 1 2 3 ／ 4 5 6 ／ 7 8 9 587412369 起始方向下（範例沒有）：下 8、左 7、上 4 1、右 2 3、下 6 9
3 ／ 1 ／ 7 7 7 ／ 7 7 7 ／ 7 7 7 777777777 全部同一個數字：只看長度——恰好 \(9\) 個字、沒有空白，少一個就是漏了中央或哪一段少走

四筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 忘記先印中央那一格：範例 1 開頭不是 9，而且尾巴會多走一步讀到陣列外面（範例 2 直接當掉）。
  • 方向編號沒照題目（例如把 \(0\) 當成上、用自己習慣的上右下左）：範例 1 印出來的正是題目敘述裡「第一步向上」那串 9385732124214968346214243；範例 2 印 058763412。
  • 右轉寫成左轉（(dir + 3) % 4 或方向表逆時針排）：範例 1 印 9123758324241264386941243、範例 2 印 014367852。自測表第 2、3 列一起看，順時針、逆時針立刻分得出來。
  • 步長寫成 \(1, 2, 3, 4, \dots\)（每段走完就加一）：第二段就多走一步，很快走出陣列外，兩個範例都直接當掉。
  • 最後一段照 len 走滿、沒有 printed < n * n 煞車：範例 1 印出 \(26\) 個字（多一個），範例 2 直接當掉。
  • 數字之間印了空白：題目明寫不要空白，範例 1 該是連在一起的 9123857…，中間夾了空白就整筆對不上。