Given an N×M 2D matrix A, let x = A[i][j]. A position (i, j) is called a special position if the sum of values within the Manhattan distance x from (i, j) modulo 10 (the remainder when divided by 10) equals x. The Manhattan distance between two points (a, b) and (c, d) is defined as ∣a−c∣+∣b−d∣.
Please write a program that outputs the total number of special positions and outputs these coordinates sorted in lexicographical order.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two positive integers N and M (1 <= N, M <= 50). The following N lines each contain M numbers, with each number ranging from 0 to 9. | The first line outputs the total number of special positions. The following 𝐾 K lines each output two positive integers representing the coordinates of the positions. Please output the special positions in lexicographical order. |
| 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 |
Thought Process
Determine the Manhattan distance boundary for each point (up, down, left, right), but do not exceed the array boundaries. The area extending from the point to the Manhattan distance boundary should form a "diamond shape." Use a for loop to sum the values within the diamond, then take the sum modulo 10. Store the coordinates of the answers in an array/vector, which can then be directly sorted.
Sample Code－ZeroJudge K732: Special Position
#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