連線計分 (APCS 2026-11 中級)

小明在一個 \(R \times C\) 的棋盤上玩連線計分遊戲。棋盤由上而下第 \(r\) 列、由左而右第 \(c\) 欄的格子記為 \((r, c)\)，列、欄都從 \(1\) 開始編號。每一格是空格、黑棋或白棋。

小明要挑一個空格，在那裡下一顆黑棋或一顆白棋。下完之後，以這顆新棋子為中心，看橫、直、左上到右下的斜線、右上到左下的斜線這四個方向：在每個方向上，從新棋子往兩邊數和它同色、而且連在一起的棋子，連同新棋子自己一共有 \(L\) 顆，\(L\) 就是這個方向的連線長度。連線必須是連續的同色棋子，中間只要隔著空格或另一種顏色的棋子就斷了。

某個方向的連線長度 \(L\) 如果至少是 \(3\)，這個方向得到 \(L^2\) 分；\(L\) 只有 \(1\) 或 \(2\) 就不得分。四個方向的分數加起來，就是這一步的得分。新棋子只有一種顏色，四個方向都用它的顏色來數。

請找出這一步最高能得幾分、要下在哪一格。如果有好幾格都能得到最高分，選列編號最小的；列編號也相同，就選欄編號最小的。

舉例來說，下圖的棋盤上已經有三顆黑棋：\((3, 2)\)、\((3, 4)\)、\((4, 3)\)。在紅框的 \((3, 3)\) 下一顆黑棋，橫的方向 \((3, 2)\)、\((3, 3)\)、\((3, 4)\) 三顆相連，得 \(3^2 = 9\) 分；直的方向 \((3, 3)\)、\((4, 3)\) 只有兩顆，不得分；兩條斜線上都只有新棋子自己一顆，也不得分。這一步共得 \(9\) 分。圖中穿過棋子的線，是有得分的方向。

輸入格式

第一行有兩個正整數 \(R\) 和 \(C\)，代表棋盤有 \(R\) 列、\(C\) 欄。

接下來有 \(R\) 行，其中第 \(r\) 行有 \(C\) 個整數，依序是第 \(r\) 列第 \(1\)～\(C\) 欄的格子：\(0\) 是空格、\(1\) 是黑棋、\(2\) 是白棋。

同一行的整數之間以一個空白隔開。

限制

• \(1 \le R \le 50\)
• \(1 \le C \le 50\)
• 棋盤上至少有一個空格。

輸出格式

輸出一行，包含三個整數 \(r\)、\(c\)、\(s\)，以一個空白隔開，代表下在 \((r, c)\) 可以得到最高分 \(s\)。如果每個空格的得分都是 \(0\)，就輸出列編號最小（列編號相同時欄編號最小）的空格與 \(0\)。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

5 5
0 0 0 0 0
0 0 0 0 0
0 1 1 0 0
1 0 1 0 0
0 0 1 0 0

範例輸出 1

2 3 25

範例解釋 1

在紅框的 \((2, 3)\) 下黑棋：直的方向 \((2, 3)\)、\((3, 3)\)、\((4, 3)\)、\((5, 3)\) 四顆相連，得 \(4^2 = 16\) 分；右上到左下的斜線 \((2, 3)\)、\((3, 2)\)、\((4, 1)\) 三顆相連，得 \(3^2 = 9\) 分；橫的和左上到右下的斜線都只有一顆，不得分。共 \(25\) 分，是全盤最高分。

範例輸入 2

4 4
1 0 1 1
2 1 2 0
2 0 1 2
0 2 2 1

範例輸出 2

4 1 18

範例解釋 2

在紅框的 \((4, 1)\) 下白棋：橫的方向 \((4, 1)\)、\((4, 2)\)、\((4, 3)\) 三顆相連，得 \(9\) 分；直的方向 \((2, 1)\)、\((3, 1)\)、\((4, 1)\) 三顆相連，也得 \(9\) 分；兩條斜線都不得分。共 \(18\) 分。

如果改在 \((3, 2)\) 下白棋，左上到右下的斜線 \((2, 1)\)、\((3, 2)\)、\((4, 3)\) 三顆相連，得 \(9\) 分，但另外三個方向都只有兩顆，不得分，這一步只有 \(9\) 分。

題目來源

APCS 2026 年 11 月中級實作題第 2 題。

官方未公布題本，題敘依考生考後回憶整理（豌豆 APCS 提供），細節可能與正式試題有出入。