語法書 / AA 競程語法書 下冊 / 第十三單元 / 二維陣列就是地圖

13.1 二維陣列就是地圖

圖 13-1:二維地圖的座標——第 i 列(橫排)第 j 行(直排)

上冊 6.9 學過二維陣列 a[i][j]:第一個中括號挑「哪一橫排」,第二個中括號挑「那一排的第幾格」。地圖題就是把題目的方格圖原封不動裝進去——一格對應一個元素

列與行:APCS 的口徑

APCS 題目一律寫「第 i 列(row)第 j 行(column)」:列是橫排、行是直排,這是台灣的用法(跟中國大陸相反)。座標 (i, j) 就是「由上數來第 i 個橫排、由左數來第 j 個直排」——先換行、再往右,和你平常用電腦打文章的順序一樣。程式裡就是 a[i][j]

讀入數字地圖與字元地圖

地圖有兩種長相。數字地圖每格是一個整數(人口、寶石數、-1 代表牆),用巢狀 vector10.3)最順手:

int R, C;
cin >> R >> C;
vector<vector<int>> a(R, vector<int>(C));   // R 列 C 行,全部初始化為 0
for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++)
        cin >> a[i][j];

字元地圖每格是一個字元(# 是牆、. 是空地),一列剛好是一個 string10.7),用 vector<string> 裝:一次讀一整列,grid[i][j] 就是第 i 列第 j 個字元。

int H, W;
cin >> H >> W;
vector<string> grid(H);
for (int i = 0; i < H; i++)
    cin >> grid[i];          // 一次讀入一整列
// grid[i][j] 是第 i 列第 j 行的字元

固定大小的陣列(int a[105][105];)當然也可以,只要把邊開得比題目上限大一點。本單元統一用 vector,因為長寬是讀進來才知道的。

例題:最大和(APCS 2016 年 10 月中級)

題目N 群數字(N \times M 的表格,1 \le N, M \le 201 \le x_i \le 256),每群選一個數字使總和 S 最大——也就是每列取最大值相加;再依序輸出被選中的數字裡能整除 S 的那些,一個都沒有就輸出 -1

這是最單純的二維陣列題:讀進來、每一列掃一遍取最大值、加總、再掃一次選出來的數字。

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));   // n 列 m 行的表格
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    vector<int> chosen(n);   // 每一列選出來的數字
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int best = a[i][0];
        for (int j = 1; j < m; j++)          // 掃過第 i 列的每一格
            best = max(best, a[i][j]);
        chosen[i] = best;
        sum += best;
    }

    cout << sum << '\n';
    bool printed = false;
    for (int i = 0; i < n; i++) {
        if (sum % chosen[i] == 0) {
            if (printed) cout << ' ';
            cout << chosen[i];
            printed = true;
        }
    }
    if (!printed) cout << -1;
    cout << '\n';
    return 0;
}

外層迴圈走「哪一列」、內層迴圈走「那一列的哪一格」,是二維陣列的標準遍歷(上冊 6.9)。輸出那段的 printed 旗標負責「數字之間一個空白、最後沒有空白」——APCS 的輸出格式向來嚴格,這種小地方也是分數。