# APCS實作題2023年6月第2題：特殊位置

> 日期：2023年9月28日
> 作者：王一哲
> 題目來源：112年6月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=k732)

<br />

## 題目

### 問題描述

給定一個 $n \times m$ 的二維矩陣 $a$，設 $x = a[i][j]$，離 $(i, j)$ 曼哈頓距離為 $x$ 內的點數值總和%10 恰為 $x$ 的稱之為特殊位置。定義兩個點 $(a, b)$ 和 $(c, d)$ 的曼哈頓距離為 $|a - c| + |b - d|$。

請寫一個程式，輸出共有幾個特殊位置，並按照字典序由小到大輸出這些位置的座標。

子問題一 60%：$n = 1$
子問題二 40%：$n \leq 50, m \leq 50$
<br />

### 輸入說明

第一行輸入兩個正整數 $n, m (1 \leq n, m \leq 50)$，接下來有 $n$ 行，每行有 $m$ 個數字，每一個數字介於 $0$ 到 $9$。

<br />

### 輸出說明

第一行輸出共有幾個特殊位置，接下來輸出 $k$ 行，每一行輸出兩個正整數代表作標點位。特殊位置請按照字典順序由小到大輸出。

<br />

### 範例一：輸入

1 8
1 2 3 4 5 6 7 8

### 範例一：正確輸出

1
0 5

<br />

### 範例二：輸入

2 3
5 2 3
4 5 6

### 範例二：正確輸出

2
0 0 
1 1

<br />

## Python 程式碼

### 方法1

這是比較單純的寫法，但是在第7 ~ 17行的程式碼需要跑4層的 for 迴圈，於 ZeroJudge 測試結果，第12筆測資開始會超時。

n, m = map(int, input().split())  # 讀取 n, m
maps = []  # 存放地圖的二維串列
for _ in range(n): maps.append(list(map(int, input().split())))  # 讀取地圖資料加到 maps
ans = []  # 儲存特殊位置用的二維串列
num = 0  # 特殊位置個數

for i in range(n):  # 依序讀取地圖的每一格資料
    for j in range(m):
        x = maps[i][j]  # 此格資料存入 x
        total = 0  # 距離小於等於 x 的資料加總
        for r in range(n):  # 依序讀取地圖的每一格資料
            for c in range(m):
                if abs(i - r) + abs(j - c) <= x:  # 如果此格距離小於等於 x
                    total += maps[r][c]  # 加總
        if total%10 == x:  # 判斷是否為特殊位置，更新 num 及 ans
            num += 1
            ans.append([i, j])

print(num)  # 印出答案
for i in range(len(ans)):
    for j in range(len(ans[i])):
        print(ans[i][j], end=" " if j < len(ans[i])-1 else "\n")

<br /><br />

### 方法2

由方法1的程式碼改寫，於內層的兩個 for 迴圈中加上 if, elif, else，跳過不可能符合跳件的位置並提早中止迴圈，可以有效地節省程式運作時間。於 ZeroJudge 測試結果，最長運算時間約為 0.7 s，使用記憶體最多約為 3.6 MB，通過測試。

n, m = map(int, input().split())  # 讀取 n, m
maps = []  # 存放地圖的二維串列
for _ in range(n): maps.append(list(map(int, input().split())))  # 讀取地圖資料加到 maps
ans = []  # 儲存特殊位置用的二維串列
num = 0  # 特殊位置個數

for i in range(n):  # 依序讀取地圖的每一格資料
    for j in range(m):
        x = maps[i][j]  # 此格資料存入 x
        total = 0  # 距離小於等於 x 的資料加總
        for r in range(n):  # 依序讀取地圖的每一格資料
            if r > i+x:  # 如果 r > i+x，這些位置一定不符合條件，中止 for 迴圈
                break
            elif r < i-x:  # 如果 r < i-x，這些位置一定不符合條件，但還要跑接下來的 r 值，繼續執行 for 迴圈
                continue
            else:
                for c in range(m):
                    if c > j+x:  # 如果 c > j+x，這些位置一定不符合條件，中止 for 迴圈
                        break
                    elif c < j-x:  # 如果 c < j-x，這些位置一定不符合條件，但還要跑接下來的 c 值，繼續執行 for 迴圈
                        continue
                    else:
                        if abs(i - r) + abs(j - c) <= x:  # 如果此格距離小於等於 x
                            total += maps[r][c]  # 加總
        if total%10 == x:  # 判斷是否為特殊位置，更新 num 及 ans
            num += 1
            ans.append([i, j])

print(num)  # 印出答案
for i in range(len(ans)):
    for j in range(len(ans[i])):
        print(ans[i][j], end=" " if j < len(ans[i])-1 else "\n")

<br /><br />

## C++ 程式碼

由 Python 程式碼方法2改寫成 C++ 版本，於 ZeroJudge 測試結果，最長運算時間約為 5 ms，使用記憶體最多約為 356 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m; cin >> n >> m;  // 讀取 n, m
    int maps[n][m];  // 存放地圖的二維陣列
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> maps[i][j];  // 讀取地圖資料加到 maps
        }
    }
    vector<vector<int>> ans;    // 儲存特殊位置用的二維串列
    int num = 0;  // 特殊位置個數

    for(int i=0; i<n; i++) {  // 依序讀取地圖的每一格資料
        for(int j=0; j<m; j++) {
            int x = maps[i][j];  // 此格資料存入 x
            int total = 0;  // 距離小於等於 x 的資料加總
            for(int r=0; r<n; r++) {  // 依序讀取地圖的每一格資料
                if (r > i+x) {  // 如果 r > i+x，這些位置一定不符合條件，中止 for 迴圈
                    break;
                } else if (r < i-x) {  // 如果 r < i-x，這些位置一定不符合條件，但還要跑接下來的 r 值，繼續執行 for 迴圈
                    ;
                } else {
                    for(int c=0; c<m; c++) {
                        if (c > j+x) {  // 如果 c > j+x，這些位置一定不符合條件，中止 for 迴圈
                            break;
                        } else if (c < j-x) {  // 如果 c < j-x，這些位置一定不符合條件，但還要跑接下來的 c 值，繼續執行 for 迴圈
                            ;
                        } else {
                            if (abs(i - r) + abs(j - c) <= x) {  // 如果此格距離小於等於 x
                                total += maps[r][c];  // 加總
                            }
                        }
                    }
                }
            }
            if (total%10 == x) {  // 判斷是否為特殊位置，更新 num 及 ans
                num++;
                ans.push_back({i, j});
            }
        }
    }

    cout << num << endl;  // 印出答案
    for(auto it = ans.begin(); it != ans.end(); it++) {
        for(auto it2 = (*it).begin(); it2 != (*it).end(); it2++) {
            cout << *it2 << " \n"[it2 == (*it).end()-1];
        }
    }
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`