連線計分 題解｜APCS 2026 年 11 月中級 第 2 題

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

const int MAX_C = 50;

int a[MAX_C + 1];                          // a[c]：第 c 欄，從 1 用起

int main() {
    int R, C;
    cin >> R >> C;                         // 子題組 1 保證 R = 1：棋盤只有一列
    for (int c = 1; c <= C; c++) cin >> a[c];

    int bestC = 0, bestS = -1;             // 最高分從 -1 開始
    for (int c = 1; c <= C; c++) {
        if (a[c] != 0) continue;           // 只能下在空格
        int score = 0;                     // 這一格的得分：黑、白兩種取大的
        for (int color = 1; color <= 2; color++) {
            int L = 1;                     // 新棋子自己
            for (int j = c - 1; j >= 1 && a[j] == color; j--) L++;   // 往左數
            for (int j = c + 1; j <= C && a[j] == color; j++) L++;   // 往右數
            if (L >= 3) score = max(score, L * L);
        }
        if (score > bestS) {               // 嚴格大於才換：同分留下欄編號小的
            bestS = score;
            bestC = c;
        }
    }
    cout << 1 << ' ' << bestC << ' ' << bestS << '\n';   // 只有一列，列編號一定是 1
    return 0;
}

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

const int MAX_R = 50;
const int MAX_C = 50;

int R, C;
int g[MAX_R + 1][MAX_C + 1];     // g[r][c]：第 r 列第 c 欄，列、欄都從 1 用起；0 空格、1 黑棋、2 白棋（放全域，函式才看得到）

// 四條線各記一個方向：橫（往右）、直（往下）、左上到右下（往右下）、右上到左下（往左下）
// 另一邊是正負號反過來的 (-dr[d], -dc[d])
const int dr[4] = {0, 1, 1, 1};
const int dc[4] = {1, 0, 1, -1};

bool inside(int r, int c) {
    return 1 <= r && r <= R && 1 <= c && c <= C;
}

// 從 (r, c) 往 (stepR, stepC) 一格一格走，數連續幾顆 color（不含 (r, c) 自己）
int countRun(int r, int c, int stepR, int stepC, int color) {
    int cnt = 0;
    r += stepR;
    c += stepC;
    while (inside(r, c) && g[r][c] == color) {
        cnt++;
        r += stepR;
        c += stepC;
    }
    return cnt;
}

int main() {
    cin >> R >> C;
    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            cin >> g[r][c];

    int bestR = 0, bestC = 0, bestS = -1;    // 最高分從 -1 開始
    for (int r = 1; r <= R; r++) {           // 外層跑列、內層跑欄：同分先比列、再比欄
        for (int c = 1; c <= C; c++) {
            if (g[r][c] != 0) continue;      // 只能下在空格
            int score = 0;                   // 這一格的得分：黑、白兩種取大的
            for (int color = 1; color <= 2; color++) {
                int total = 0;               // 下這個顏色：四條線的分數加起來
                for (int d = 0; d < 4; d++) {
                    int L = 1 + countRun(r, c, dr[d], dc[d], color)
                              + countRun(r, c, -dr[d], -dc[d], color);
                    if (L >= 3) total += L * L;
                }
                score = max(score, total);
            }
            if (score > bestS) {             // 嚴格大於才換
                bestS = score;
                bestR = r;
                bestC = c;
            }
        }
    }
    cout << bestR << ' ' << bestC << ' ' << bestS << '\n';
    return 0;
}