給定一個 N＊M 的二維矩陣 A，設 x = A[i][j]，離 (i, j) 曼哈頓距離為 x 內的點數值總和 % 10 (除以 10 後的餘數) 恰為 x 的稱之為特殊位置。定義兩個點 (a, b) 和 (c, d) 的曼哈頓距離為 |a – c| + |b – d|。
請寫一個程式，輸出共有幾個特殊位置，並按照字典序由小到大輸出這些位置的座標。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行輸入兩個正整數 N 和 M (1 <= N, M <= 50)，接下來有 N 行，每行有 M 個數字，每一個數字介於 0 到 9 。 | 第一行輸出共有幾個特殊位置，接下來輸出 K 行，每一行輸出兩個正整數代表作標點位。特殊位置請按照字典順序由小到大輸出。 |
| 1 8 1 2 3 4 5 6 7 8 | 1 0 5 |
| 2 3 5 2 3 4 5 6 | 2 0 0 1 1 |
解題思路
判斷每個點的曼哈頓距離邊界 (上下左右)，但是不能超過陣列的邊界。從點延伸到曼哈頓距離邊界應該會是一個「菱形的樣子」，使用 For迴圈 將菱形中的數值加在一起後對 10 取餘數即可。座標的答案可以存放在 陣列/Vector 中，這樣可以直接用 Sort 排序。
範例程式碼－ZeroJudge K732: 特殊位置
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, int> axis (int a, int b)
{
pair<int, int>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<vector<int>>num;
for (int i = 0; i<N; i++)
{
vector<int>hi;
for (int j = 0; j<M; j++)
{
int tmp;
cin >> tmp;
hi.push_back(tmp);
}
num.push_back(hi);
}
vector<pair<int, int>>ans;
for (int i = 0; i<N; i++)
{
for (int j = 0; j<M; j++)
{
int x = num[i][j];
int left = 0, right = M-1;
if (j - x >= 0) left = j - x;
if (j + x <= M-1) right = j + x;
int enumeration = 0;
for (int k = left; k<=right; k++)
{
int up = i-(x - abs(j-k));
int down = i+(x - abs(j-k));
if (up <= 0) up = 0;
if (down >= N-1) down = N-1;
for (int l = down; l>=up; l--)
{
enumeration += num[l][k];
}
}
if (enumeration % 10 == x)
{
ans.push_back(axis(i, j));
}
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (int i = 0; i<ans.size(); i++)
{
cout << ans[i].first << " " << ans[i].second << "\n";
}
}
//ZeroJudge K732
//Dr. SeanXD