特殊位置 (APCS 2023-06 中級)

考慮一個二維正整數陣列 \(A\)，有 \(n\) 列（row）及 \(m\) 行（column）。陣列 \(A\) 中第 \(i\) 列第 \(j\) 行的元素 \(A[i][j]\)。兩個元素 \(A[i][j]\) 與 \(A[s][t]\) 的距離定為 \(|i - s| + |j - t|\)，也就是列註標差的絕對值加上與行註標差的絕對值。

對於一個元素 \(A[i][j] = x\)，若與其距離不超過 \(x\) 的元素總和（包含 \(A[i][j]\)）除以 \(10\) 的餘數與 \(x\) 除以 \(10\) 的餘數相同，則我們稱 \((i, j)\) 為一特殊位置；注意，在計算此總和時，超出陣列範圍的元素不予計算。今給定一陣列，你的任務要找出陣列 \(A\) 中特殊位置的總數以及每個特殊位置；一個位置以兩個數字表示，分別代表其列註標與行註標。

舉例來說，考慮下列陣列 \(A\)：

其中 \(A[0][0] = 1\)，與其距離 \(1\) 以內的只有三個元素：其本身、右方的 \(3\) 與下方的 \(1\)，其總和為 \(1 + 3 + 1 = 5\)，其除以 \(10\) 的餘數與 \(A[0][0]\) 除以 \(10\) 的餘數不同，故 \((0, 0)\) 並非一特殊位置。而 \(A[2][3] = 2\)，與其距離 \(2\) 以內有 \(13\) 個元素，如圖中陰影處所示，其元素總和為 32，除以 \(10\) 的餘數為 \(2\)，與 \(A[2][3]\) 除以 \(10\) 的餘數相同，故 \((2, 3)\) 為一特殊位置。此例之特殊位置共有 \(4\) 個，分別為 \((0, 2)\)、\((1, 3)\)、\((2, 3)\) 以及 \((3, 3)\)。

輸入格式

輸入第一行有兩個正整數 \(n\) 與 \(m\)，\(1 \le n, m \le 50\)，代表陣列的列數與行數。接下去有 \(n\) 行，每行有 \(m\) 個整數，表示陣列的內容，其順序為由上而下，由左至右。同一行的兩數字之間以一個空白間隔。陣列內的數字均為小於 \(10\) 的正整數。

輸出格式

第一行是一個整數 \(k\)，表示所求之特殊位置總數。接下來 \(k\) 行，每行有兩個整數，依序表示一個特殊位置的列註標與行註標。輸出時，列註標較小的特殊位置先輸出，若兩個特殊位置的列註標相同，則先輸出行註標較小者。

範例輸入 1

1 5
3 1 4 5 1

範例輸出 1

2
0 0
0 2

範例輸入 2

5 6
1 3 4 1 3 1
1 1 4 1 3 1
1 1 3 2 5 3
4 3 3 1 4 1
5 2 1 1 1 1

範例輸出 2

4
0 2
1 3
2 3
3 3

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過測資筆數給分。其中：

• 第 1 子題組 60 分：\(n = 1\)。
• 第 2 子題組 40 分：無額外限制。

題目來源

APCS 程式實作中級題本範例，程式實作 2023 年 6 月。

• APCS 官方中級題本範例
• ZeroJudge k732