ZeroJudge K732: 特殊位置

題目敘述

每筆測資第一行有兩個正整數N和M，接下來會有一個N乘以M的二維陣列代表每個座標上的值。如果一個點他的曼哈頓距離內的點的值總和對10取餘數剛好為該點的數值，此為特殊位置。定義兩個點 (a, b) 和 (c, d) 的曼哈頓距離為 |a - c| + |b - d|。要求輸出二維陣列中有多少個特殊位置並輸出這個點的位置 (需經過排序)。

範例輸入 #1

1 8

1 2 3 4 5 6 7 8

範例輸出 #1

1

0 5

範例輸入 #2

2 3

5 2 3

4 5 6

範例輸出 #2

2

0 0 

1 1

解題思路

判斷每個點的曼哈頓距離邊界 (上下左右)，但是不能超過陣列的邊界。從點延伸到曼哈頓距離邊界應該會是一個菱形的樣子，使用For迴圈將菱形中的數值加在一起後對10取餘數即可。座標的答案可以存放在Vector<Pair<int, int>>中，這樣可以直接用Sort排序。

解題程式碼如下 (僅供參考)：

#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";
    }
}