13.1 二維陣列就是地圖
上冊 6.9 學過二維陣列 a[i][j]:第一個中括號挑「哪一橫排」,第二個中括號挑「那一排的第幾格」。地圖題就是把題目的方格圖原封不動裝進去——一格對應一個元素。
¶列與行:APCS 的口徑
APCS 題目一律寫「第 i 列(row)第 j 行(column)」:列是橫排、行是直排,這是台灣的用法(跟中國大陸相反)。座標 (i, j) 就是「由上數來第 i 個橫排、由左數來第 j 個直排」——先換行、再往右,和你平常用電腦打文章的順序一樣。程式裡就是 a[i][j]。
¶讀入數字地圖與字元地圖
地圖有兩種長相。數字地圖每格是一個整數(人口、寶石數、-1 代表牆),用巢狀 vector(10.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];
字元地圖每格是一個字元(# 是牆、. 是空地),一列剛好是一個 string(10.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 20,1 \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 的輸出格式向來嚴格,這種小地方也是分數。