# APCS 202306 第2題 特殊位置 (ZeroJudge k732)
[ZJ題目連結](https://zerojudge.tw/ShowProblem?problemid=k732) (此題解先說明方法再揭示範例程式，包含python與C++)
## 方法說明
對於一個$n\times m$的二維陣列(矩陣)$a$，這題要計算那些是所謂的*特殊點*，最後輸出特殊點的個數以及每一個特殊點的位置。
設 $x = a[i][j]$，離$(i,j)$曼哈頓距離為$x$內的點數值總和 % 10 恰為 $x\%10$的稱之為特殊位置。定義兩個點$(a, b)$ 和 $(c, d)$ 的曼哈頓距離為 $|a - c| + |b - d|$。
**這題只要枚舉就可以了**。
我們枚舉所有的點$x = a[i][j]$，找出所有滿足距離要求的點並將其加總，將加總的結果來判斷是否為特殊點。對於$a[i][j]$，若$a[s][t]$距離在$x$之內，則必然 $i-x\leq s\leq i+x$且$j-x\leq t\leq j+x$。需要注意的是上述條件反之未必然，有可能超出界線或距離超過$x$，所以我們雙迴圈枚舉在此範圍的點，並且以if來判斷是否合乎距離需求。
對於輸出，因為需要先輸出點數再輸出各點位置，我們必須先將找出的點放在一個容器(list or array)中，題目要求的順序是*字典序*，也就是row-major，由上而下，由左至右。我們便依此順序來枚舉。主要流程如下：
```
輸入矩陣
準備一個放答案的容器ans
for i from 0 to n-1
for j from 0 to m-1
x = a[i][j]
total = 0 用來加總的變數
for s from i-x to i+x
for t from j-x to j+x
if s,t未出界 且 abs(i-s)+abs(j-t)<=x then
total += a[s][t]
end if
end for-t
end for-s
if total%10 == x%10 then
將(i,j)放入ans中
end if
end for j
end for-i
輸出答案
```
**小技巧：** 為什麼枚舉就可以呢？因為是APCS的第二題不會太需要時間複雜度的思考(大誤)。上面是開玩笑，說正格的，這題n,m不超過50，矩陣元素$x$不超過9，我們可以估算最多需要加總的個數是$50\times 50\times 19\times 19 < 10^6$，現在一般電腦一秒鐘python大概$10^6$，C++ $10^7$這樣的運算不會有問題。
這題是可以算得技巧一些來加快速度，但並不需要。
## 第一子題
雖然這題不困難，我們還是講一下第一子題的範例程式。第一子題是一維陣列(n=1)，因此對於任何一點，只需要用一層迴圈找出左右範圍即可，曼哈頓距離也不需要計算。以下是Python與C++的範例程式。
### Python code
```python=
n,m = map(int,input().split())
# n= 1
mat = [int(x) for x in input().split()]
point = []
for j in range(m):
x = mat[j]
total = 0
for t in range(j-x,j+x+1):
if 0<=t<m:
total += mat[t]
# total = sum(mat[max(0,j-x):min(m,j+x+1)])
if (total-x)%10==0:
point.append(j)
print(len(point))
for x in point:
print(0,x)
```
其中第7~10行的程式也可以寫作第11行的寫法。
第3行輸入一行空白間隔的整數的方法初學者需要學一下。
留意list加入一個元素用append(第13行)，list的元素個數可以用len(pooint)求出(第15行)。
### C code
這題C與C++幾乎沒有甚麼差異，以下為第一子題C的範例程式。
```c=
// s1, row=1
#include <stdio.h>
int main() {
int n,m, i,j,a[101];
int sol[101],k=0;
scanf("%d%d",&n,&m); //n==1
for (i=0; i<m; i++) scanf("%d",&a[i]);
for (i=0; i<m; i++) {
int total=0,first=i-a[i],last=i+a[i];
if (first<0) first = 0;
if (last>=m) last = m-1;
for (j=first; j<=last; ++j) total += a[j];
if ((total-a[i])%10 == 0) {
sol[k++] = i;
}
}
// output
printf("%d\n",k);
for (i=0;i<k;i++) printf("0 %d\n",sol[i]);
return 0;
}
```
第9~11行決定要加總的範圍後，第12行做加總，初學者可留意第14行將答案放入陣列中的方法，這裡的k就是陣列sol中元素的個數。
## 完全解
以下是Python完全解的範例程式。第4行每次讀入一行空白間隔整數並將它放在list中。第17行將點座標放入point中，可以用tuple (i,j)或是list [i,j]。第20行將座標從point中取出列印時，可以直接這樣寫
for r,c in point:
point中每個元素都是2個元素的tuple，例如(0,3)，取出時會自動unpacking執行 r=0; c=3。
### Python code
```python=
n,m = map(int,input().split())
mat = []
for i in range(n):
mat.append([int(x) for x in input().split()])
point = [] # answer
for i in range(n):
for j in range(m):
x = mat[i][j]
total = 0
#enumerate all (s,t) in range
for s in range(i-x,i+x+1):
for t in range(j-x,j+x+1):
if 0<=s<n and 0<=t<m and abs(i-s)+abs(j-t)<=x:
total += mat[s][t]
if (total-x)%10==0:
point.append((i,j))
# output answer
print(len(point))
for r,c in point:
print(r,c)
```
### C++ code
接著是C++的範例程式。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, i,j,m,r,c;
int a[50][50];
int srow[2500],scol[2500],k=0;
cin >> n>> m;
for (i=0;i<n;i++) {
for (j=0;j<m;j++) {
cin >> a[i][j];
}
}
for (r=0; r<n; r++) {
for (c=0; c<m; c++) {
int total=0,x=a[r][c];
for (i=r-x; i<=r+x; i++){
if (i<0 || i>=n) continue;
for (j=c-x; j<=c+x; j++) {
if (j<0 || j>=m) continue;
if (abs(i-r)+abs(c-j)<=x)
total += a[i][j];
}
}
if ((total-x)%10==0) {
srow[k]=r,scol[k]=c;
k++;
}
}
}
// output
cout <<k<<'\n';
for (i=0;i<k;i++) {
cout << srow[i]<<' '<<scol[i]<<'\n';
}
return 0;
}
```
###### tags: `apcs`
Sign in with Wallet
Connect another wallet