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

f148. 2. 定向越野 (Orienteering)

官網題目

題目描述

• 某大學最近開了一堂定向越野課，因應期末考，老師不想給同學太多壓力，
  所以老師出給同學們一項任務，完成後就能獲得加分機會。老師會給同學一張地
  圖，地圖上有一些目標，老師會指定要搜索的目標數量。搜索時有一個特殊條件：
  必須依照字典序（即 a, b, c, …, x, y, z）來進行探索。

• 假設今天場上有兩個任務目標 a 和 b，且老師要求之搜尋數量恰好為 2，則
  學生們必須先找尋到目標 a，才能繼續前往目標 b。

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

輸入說明

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

輸出說明

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

範例輸入/出

輸入範例 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

解題思路

1. 讀取輸入

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

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

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

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

   • 如果非零字母的數量少於 targetOfNum ( 變數名稱，用來計算達成目標所需的字母數量 )，輸出 "Mission fail."，表示無法找到足夠的字母。
   • 如果數量符合條件則進行之後的動作。

4. 排序字母並輸出結果：

   • 將 letters 按照字母的順序排序。( 使用 sort )
   • 輸出排序後的字母的位置，利用先前儲存的座標位置。

程式碼

#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;
}

成果截圖

• 

補充

• 如果需要儲存二維平面上的一個點，同時儲存 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/

心得

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