搬家 題解｜APCS 2023 年 10 月中高級 第 3 題

前置知識

這題的核心（「兩邊都有開口才相連」怎麼寫成判斷式）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

  • 二維地圖的走訪：出界判斷、方向表 dr[]／dc[]、枚舉鄰格。
  • BFS 找連通塊：NTUCPC Guide〈BFS〉——要帶走的是「從一格出發，用佇列把走得到的格子全部標記，標記過的不再進佇列；每一塊只從一格出發一次」；吳邦一《AP325》第 7 章 7.2.2「BFS」把「找 connected component」列為 BFS 的基本用途（教材 PDF 第 236～241 頁；Python 版第 7 章（I）），例題 P-7-3 機器人走棋盤（第 248～250 頁）示範把方格當成圖來走。
  • DFS（只有最後的「另一種做法」會用到）：NTUCPC Guide〈DFS〉。

簡潔題意

\(n \times m\) 的格子，每格一個字元代表那根水管的開口方向：F 右、下，H 左、右，7 左、下，I 上、下，X 上、下、左、右，L 右、上，J 左、上，0 沒有水管。上下或左右相鄰的兩根水管，彼此相對的方向都有開口才算相連。求最大的連通塊有幾根水管；完全沒有水管就輸出 \(0\)（\(1 \le n, m \le 500\)）。

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

  • 子題組 1（\(60\) 分）：不會出現 X。
  • 子題組 2（\(40\) 分）：無額外限制。

把水管變成圖：兩邊都要朝對方開口才有邊

每根水管是一個點；相鄰兩根水管之間有沒有邊，要看兩件事：我這邊往那個方向有沒有開口、對方往回來的方向有沒有開口。只檢查一邊不夠——範例 2 的 \((2, 2)\) 是 7，往左有開口，但左邊的 I 只有上下開口，兩根並不相連（圖 1）。

圖 1：範例 2 每根水管的開口，兩邊都開口的用粗線相連、只有單邊開口的標紅，最大連通塊 9 根

把方向編號成 \(0\) 上、\(1\) 右、\(2\) 下、\(3\) 左，對面的方向就是 \((d + 2) \bmod 4\)。「字元 ch 往方向 \(d\) 有沒有開口」直接查表：往上有開口的字元是 I、L、J、X，往右是 F、H、L、X，往下是 F、7、I、X，往左是 H、7、J、X——四個字串，用 find 查字元在不在裡面就好。0 在四個字串裡都不出現，所以它自然沒有任何開口。

BFS 數每一塊

從每一根還沒標記過的水管出發做一次 BFS：拿出一格，試四個方向，「我有開口、沒出界、對方也朝我開口、對方還沒標記」四個條件都成立才把鄰格標記並推進佇列。一次 BFS 推進佇列的格子數就是這一塊的大小，全部取最大。

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

const int MAX_N = 500;
int n, m;
string grid[MAX_N];
bool visited[MAX_N][MAX_N];
const int dr[4] = {-1, 0, 1, 0};  // 方向 0 上、1 右、2 下、3 左
const int dc[4] = {0, 1, 0, -1};
const string OPEN[4] = {"ILJX", "FHLX", "F7IX", "H7JX"};   // 往上／右／下／左有開口的字元

bool opens(char ch, int d) {      // 字元 ch 往方向 d 有沒有開口
    return OPEN[d].find(ch) != string::npos;
}

int bfs(int sr, int sc) {         // 從 (sr, sc) 出發，回傳這個連通塊有幾根水管
    queue<pair<int, int>> q;
    q.push({sr, sc});
    visited[sr][sc] = true;
    int count = 0;
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        count++;
        for (int d = 0; d < 4; d++) {
            if (!opens(grid[r][c], d)) continue;                 // 自己這邊要有開口
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (!opens(grid[nr][nc], (d + 2) % 4)) continue;     // 對方也要朝著我開口
            if (visited[nr][nc]) continue;
            visited[nr][nc] = true;
            q.push({nr, nc});
        }
    }
    return count;
}

int main() {
    cin >> n >> m;
    for (int r = 0; r < n; r++) cin >> grid[r];
    int answer = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == '0' || visited[r][c]) continue;    // 沒有水管、或已經算進某一塊
            answer = max(answer, bfs(r, c));
        }
    }
    cout << answer << endl;
    return 0;
}

visited 是全域的：每一格只會被推進佇列一次、每次拿出來只看四個方向，全部加起來 \(O(nm)\)，\(500 \times 500\) 本站實測 \(0.03\) 秒。answer 從 \(0\) 起算，整張圖都是 0 時外層迴圈一次 BFS 都不會做，直接印 \(0\)。

子題組 1 和子題組 2 用的是同一份程式：X 只是「四個方向都有開口」的字元，查表字串裡多一個字母而已，\(100\) 分穩穩到手。

測過再交：範例裡沒有「只有單邊開口」的陷阱被抓出來

範例 2 其實有兩處單邊開口（圖 1 的紅色），但只檢查自己這邊的錯誤程式剛好也印 \(9\)（見常犯錯誤）。沒蓋到的還有：完全沒有水管、繞成一圈的水管、X 四個方向都接到別人，以及最大盤面全部相連（驗 visited 全域、速度）。

輸入 正確輸出 這一筆在測什麼
1 1／0 0 沒有水管要印 \(0\)
1 2／HI 1 H 朝右有開口、I 沒朝左開口：單邊開口不算相連
1 3／HF7 2 H 與 F 不相連（F 不朝左開）、F 與 7 相連：不是「相鄰都不是 0 就相連」
2 2／F7／LJ 4 四根繞成一圈：BFS 不會重複數
3 3／0I0／HXH／0I0 5 X 四個方向都接到別人
用程式造：\(500 \times 500\) 全部是 X 250000 全部相連成一塊：visited 要全域，每格只進佇列一次

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

另一種做法：DFS

把「用佇列擴散」換成「遞迴往下走」：dfs(r, c) 標記自己，對四個方向做同樣的四個檢查，過了就遞迴進去，回傳值是這一趟標記了幾格。判斷式和 BFS 版一模一樣，只是換了走的順序。

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

const int MAX_N = 500;
int n, m;
string grid[MAX_N];
bool visited[MAX_N][MAX_N];
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
const string OPEN[4] = {"ILJX", "FHLX", "F7IX", "H7JX"};

bool opens(char ch, int d) {
    return OPEN[d].find(ch) != string::npos;
}

int dfs(int r, int c) {           // 回傳從 (r, c) 走得到、還沒算過的水管數
    visited[r][c] = true;
    int count = 1;
    for (int d = 0; d < 4; d++) {
        if (!opens(grid[r][c], d)) continue;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
        if (!opens(grid[nr][nc], (d + 2) % 4)) continue;
        if (visited[nr][nc]) continue;
        count += dfs(nr, nc);
    }
    return count;
}

int main() {
    cin >> n >> m;
    for (int r = 0; r < n; r++) cin >> grid[r];
    int answer = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == '0' || visited[r][c]) continue;
            answer = max(answer, dfs(r, c));
        }
    }
    cout << answer << endl;
    return 0;
}

兩種都是滿分，但要知道一件事：遞迴的深度最多等於一塊的大小，\(500 \times 500\) 全部相連時是 \(250000\) 層。本站的沙箱不限制堆疊大小，官方測資全過；在堆疊預設 \(8\) MB 的環境（例如自己電腦的終端機）跑，\(500 \times 500\) 全 X 的測資會因為堆疊溢位當掉。兩種都會寫的話，這題 BFS 比較穩。

常犯錯誤
  • 只檢查自己這邊有開口，沒檢查對方有沒有朝我開口：兩個範例都過（範例 2 的兩處單邊開口，剛好都是從先算到的那一塊「看不到」的方向），計分測資掛 \(4\) 筆；自測表第 2 列印 2、第 3 列印 3。
  • 相鄰兩格都不是 0 就當相連：範例 1 印 12、範例 2 印 10。
  • 對面的方向算錯（例如寫成 3 - d）：範例 1 印 2。
  • 忘了 X（沿用子題組 1 沒有 X 的查表）：範例 1 過、範例 2 印 5；計分測資掛 \(6\) 筆。
  • 每次 BFS 之前把 visited 清掉（等於每一格都重新搜一次）：兩個範例都過，\(500 \times 500\) 全相連的測資要做 \(250000\) 次、每次 \(250000\) 格的 BFS，本站實測跑 \(2\) 分鐘都跑不完，計分測資掛 \(3\) 筆（超時）。
  • answer 初值設 \(1\)，或把 0 也當成一根水管：兩個範例都過，整張圖都是 0 時印 1；自測表第 1 列抓到，計分測資掛 \(2\) 筆。