ZeroJudge K732: 特殊位置

給定一個 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
ZeroJudge K732 範例測資

解題思路

判斷每個點的曼哈頓距離邊界 (上下左右)，但是不能超過陣列的邊界。從點延伸到曼哈頓距離邊界應該會是一個「菱形的樣子」，使用 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
標籤

相關文章

發佈留言