# ZeroJudge f148. 2. 定向越野 (Orienteering)

<br>

> [f148. 2. 定向越野 (Orienteering)](https://zerojudge.tw/ShowProblem?problemid=f148)

> [官網題目](https://tpmso.org/toi/wp-content/uploads/question/202006/Orienteering.pdf)

<br>

## 題目描述 :+1:

* 某大學最近開了一堂定向越野課，因應期末考，老師不想給同學太多壓力，
所以老師出給同學們一項任務，完成後就能獲得加分機會。老師會給同學一張地
圖，地圖上有一些目標，老師會指定要搜索的目標數量。搜索時有一個特殊條件：
必須依照字典序（即 a, b, c, …, x, y, z）來進行探索。
* 假設今天場上有兩個任務目標 a 和 b，且老師要求之搜尋數量恰好為 2，則
學生們必須先找尋到目標 a，才能繼續前往目標 b。

* 老師有可能粗心出錯題目，或者是記錯自己所放置的目標數量，導致無法達
成任務。給定地圖資訊及需搜索之目標數量，請你撰寫程式依序輸出目標的位置，
或者判定任務無法達成。

<br>

## 輸入說明 :+1:

* 輸入的第一行有兩個整數 W、H (1 <= W, H <= 10)，代表的是此地圖由上而下
有 W 列，由左而右共有 H 行，總共劃分成 W×H 個方格。第二行會有一個整數
N (1 <= N <= 26)，代表的是老師要求尋找的目標數量。
* 接下來的 W 列，每列有 H 個可能為 0 或小寫英文字母的字元，字元間以一
個空白隔開。0 代表此處是空地，小寫英文字母則代表是目標。英文字母不會重
複出現。此地圖最左上角的位置為 (0, 0)，最右下角的位置為 (W−1, H−1)。
<br>

## 輸出說明 :+1:

* 請依照字典序輸出目標之位置，只需印出指定的目標數量。如果場地上可供
尋找的目標數量小於指定的目標數量，代表這個任務無法被達成，請輸出
Mission fail.（範例三）。

<br>

## 範例輸入/出 :+1:

輸入範例 1
5 5 
5
0 0 a 0 0
0 b 0 0 0
c 0 0 0 0
0 d 0 0 0
0 0 e 0 0

輸出範例 1
0 2
1 1
2 0
3 1
4 2

輸入範例 2
2 2
4
g e
f d

輸出範例 2  
1 1
0 1
1 0
0 0

輸入範例 3
4 4
5
z 0 0 0
c 0 0 0
a 0 0 0
g 0 0 0
    
輸出範例 3
Mission fail.

輸入範例 4
3 3
6
x c a
b 0 y
0 g 0
    
輸出範例 4
0 2
1 0
0 1
2 1
0 0
1 2

輸入範例 5
5 5
10
f g h i j
k l m n o
a b c d e
p q r s t
u v w x y

輸出範例 5
2 0
2 1
2 2
2 3
2 4
0 0
0 1
0 2
0 3
0 4

<br>

## 解題思路 :+1:
1. **讀取輸入**

* 首先讀取二維陣列的大小為 n * m 的元素。

2. **讀取地圖並收集字母** :

* 宣告一個 char 類型的二維陣列 map 來存儲輸入矩陣( map是矩陣名稱 )。
* 宣告一個 vector ，名字為 letters，用來存儲字母及其在地圖中的位置。
* 使用兩個嵌套的 for 循環遍歷整個輸入矩陣，讀取每個位置的字母。如果該位置的字母不是 '0'，就將字母及其位置存入 letters。
* 同時計算非零字母的數量。以便後來確認是否達成任務。

4. **檢查字母數量是否足夠**：

* 如果非零字母的數量少於 targetOfNum ( 變數名稱，用來計算達成目標所需的字母數量 )，輸出 "Mission fail."，表示無法找到足夠的字母。
* 如果數量符合條件則進行之後的動作。
5. **排序字母並輸出結果**：
* 將 letters 按照字母的順序排序。( 使用 sort )
* 輸出排序後的字母的位置，利用先前儲存的座標位置。

## 程式碼 :+1:

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    char map[10][10];

    int targetOfNum;
    cin >> targetOfNum;

    vector<pair<int, pair<int, int>>> letters; 
    int count = 0;

    // 輸入矩陣
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] != '0')
            {
                letters.push_back(make_pair(map[i][j], make_pair(i, j)));
                count++;
            }
        }
    }
    // 判斷 + 輸出結果
    if (count < targetOfNum)
    {
        cout << "Mission fail.\n";
    }
    else
    {
        sort(letters.begin(), letters.end()); 
        
        for (int i = 0; i < targetOfNum; i++)
        {
            cout << letters[i].second.first << " " << letters[i].second.second << endl;
        }
    }

    return 0;
}

## 成果截圖 :+1:

* 

## 補充 :sunglasses:

::: info
* 如果需要儲存二維平面上的一個點，同時儲存 x, y 兩個整數，但又需要進行 sort 之類會改變位置的操作就可以利用 ==pair==
* pair 可以用於將兩個不同類型 ( 或是同類型 ) 的值關聯在一起，以便一起傳遞、返回或儲存。

pair<int, pair<int,int>> p1
pair<int, vector<int>> p2;
pair<int, vector<pair<int, vector>>> ..... // (X)

* 

* 範例
> vector<pair<int, pair<int, int>>> letters;

* pair<int, int> 用來除存 x , y 座標
* pair<int, pair<int, int>> 用來儲存字母和他的 x , y 座標
P.S. 字母用 int 存是使用 ASCII 碼來存

> letters.push_back(make_pair(map[i][j], make_pair(i, j)));

* make_pair(i, j) 用於指派 x , y 座標的變數成一個 pair
* make_pair(map[i][j], make_pair(i, j)) 用於指派字母和 x , y 座標的變數成一個 pair

> cout << letters[i].second.first << " " << letters[i].second.second << endl;
* letters[i].second.first 顯示的是 **make_pair(i, j)** 的 ==i==
* letters[i].second.second 顯示的是 **make_pair(i, j)** 的 ==j==
> 參考網站 : https://emanlaicepsa.github.io/2020/12/02/0-18/
:::

<br>

## 心得 :+1:

* 第三次寫解題報告，希望可以幫助到人~~
* 如果有錯或是不妥的部分，請留言告訴我，感恩~~

<br>