Board logo

標題: 202412新手2-香料 (Spices) [打印本頁]
作者: may    時間: 2025-1-27 22:03     標題: 202412新手2-香料 (Spices)

問題敘述
小希最近喜歡上烹飪，特別是各式各樣的香料料理，他今天又到超市去購買所需的材料。超市有一整區的香料櫃，他要根據食譜找到所有香料。請寫一個程式幫他找到香料所在位置。
[attach]20602[/attach]
[attach]20603[/attach]
作者: may    時間: 2025-1-27 22:17

  1. #include <bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <vector>
  4. using namespace std;

  6. int main() {
  7.     // 輸入香料數量
  8.     int N;
  9.     cin >> N;

  11.     // 儲存要找的香料編號
  12.     vector<int> spicesToFind(N);
  13.     for (int i = 0; i < N; i++) {
  14.         cin >> spicesToFind[i];
  15.     }

  17.     // 輸入貨架資訊
  18.     int R, C;
  19.     cin >> R >> C;

  21.     // 儲存貨架香料編號
  22.     vector<vector<int>> shelves(R, vector<int>(C));
  23.     for (int i = 0; i < R; i++) {
  24.         for (int j = 0; j < C; j++) {
  25.             cin >> shelves[i][j];
  26.         }
  27.     }

  29.     // 找尋每個香料的位置
  30.     for (int spice : spicesToFind) {
  31.         bool found = false;
  32.         for (int i = 0; i < R; i++) {
  33.             for (int j = 0; j < C; j++) {
  34.                 if (shelves[i][j] == spice) {
  35.                     // 找到香料，輸出其位置
  36.                     cout << i + 1 << " " << j + 1 << endl;
  37.                     found = true;
  38.                     break;
  39.                 }
  40.             }
  41.             if (found) break;
  42.         }
  43.         if (!found) {
  44.             // 如果找不到香料，輸出 -1
  45.             cout << -1 << endl;
  46.         }
  47.     }

  49.     return 0;
  50. }
  51. /*
  52. 輸入範例1
  53. 3
  54. 2 5 7
  55. 3 3
  56. 1 2 3
  57. 4 5 6
  58. 7 8 9
  59. 輸出範例1
  60. 1 2
  61. 2 2
  62. 3 1

  64. 輸入範例2
  65. 5
  66. 1 6 8 21 20
  67. 4 5
  68. 2 7 9 3 20
  69. 1 5 8 12 13
  70. 4 14 19 6 11
  71. 18 16 17 15 10
  72. 輸出範例2
  73. 2 1
  74. 3 4
  75. 2 3
  76. -1
  77. 1 5
  78. */
複製代碼
作者: may    時間: 2025-1-27 22:26

使用雜湊表（unordered_map）可以大幅提高搜尋效率，將貨架上香料的位置儲存在雜湊表中，查詢香料位置的時間複雜度從
O(R×C) 降為 O(1)。

以下是完整的程式碼，結合雜湊表的實作：
  1. #include <bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <unordered_map>
  4. //#include <vector>
  5. using namespace std;

  7. int main() {
  8.     // 輸入香料數量
  9.     int N;
  10.     cin >> N;

  12.     // 儲存要找的香料編號
  13.     vector<int> spicesToFind(N);
  14.     for (int i = 0; i < N; i++) {
  15.         cin >> spicesToFind[i];
  16.     }

  18.     // 輸入貨架資訊
  19.     int R, C;
  20.     cin >> R >> C;

  22.     // 使用雜湊表儲存香料位置
  23.     unordered_map<int, pair<int, int>> spicePosition;
  24.     for (int i = 0; i < R; i++) {
  25.         for (int j = 0; j < C; j++) {
  26.             int spice;
  27.             cin >> spice;
  28.             // 將香料位置存入雜湊表，位置以 1 為基底
  29.             spicePosition[spice] = {i + 1, j + 1};
  30.         }
  31.     }

  33.     // 查找每個要找的香料位置
  34.     for (int spice : spicesToFind) {
  35.         if (spicePosition.find(spice) != spicePosition.end()) {
  36.             // 若香料存在於雜湊表，輸出其位置
  37.             cout << spicePosition[spice].first << " " << spicePosition[spice].second << endl;
  38.         } else {
  39.             // 若找不到香料，輸出 -1
  40.             cout << -1 << endl;
  41.         }
  42.     }

  44.     return 0;
  45. }
  46. /*
  47. 輸入範例1
  48. 3
  49. 2 5 7
  50. 3 3
  51. 1 2 3
  52. 4 5 6
  53. 7 8 9
  54. 輸出範例1
  55. 1 2
  56. 2 2
  57. 3 1

  59. 輸入範例2
  60. 5
  61. 1 6 8 21 20
  62. 4 5
  63. 2 7 9 3 20
  64. 1 5 8 12 13
  65. 4 14 19 6 11
  66. 18 16 17 15 10
  67. 輸出範例2
  68. 2 1
  69. 3 4
  70. 2 3
  71. -1
  72. 1 5
  73. */
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2