最小化透過給定源點到達目的地所需的字串定義的步驟

最小化由給定來源到達目的地所需的字串定義的步驟是電腦科學中的常見問題。它涉及根據一系列方向找到從起點到目的地點的最短路徑。在本文中，我們將討論如何用 C 解決這個問題，提供一個範例，並討論測試案例。

問題陳述

給定 2D 平面上的起點 (x, y) 和一系列方向 (N, S, E, W)，我們需要找到到達目的地點 (x', y') 的最短路徑從起點開始。字串中的每個字元代表我們應該移動的方向。例如，如果字串是“NNSE”，則我們需要向北方向移動兩步，向南方向移動一步，向東方向移動一步。我們只能在四個基本方向上移動，而無法移動到位面之外。

方法

為了解決這個問題，我們需要從起始點開始對二維平面進行廣度優先搜尋（BFS）遍歷。在遍歷過程中，對於每個訪問到的點，我們需要計算到達該點所需的步數。如果在遍歷過程中遇到目標點，我們會返回到達該點所需的步數。

範例

以下的C 程式碼實作了上述方法。

#include<bits/stdc++.h>
using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int minSteps(string s, int x, int y) {
   int n = s.size();
   int curr_x = 0, curr_y = 0, steps = 0;
   unordered_map<int, unordered_map<int, bool>> visited;
   visited[0][0] = true;
   for(int i = 0; i < n; i++) {
      char c = s[i];
      if(c == 'N') curr_y++;
      else if(c == 'S') curr_y--;
      else if(c == 'E') curr_x++;
      else if(c == 'W') curr_x--;
      if(visited[curr_x][curr_y]) continue;
      visited[curr_x][curr_y] = true;
      steps++;
   }
   int dist = abs(x - curr_x) + abs(y - curr_y);
   return (dist <= steps && (steps - dist) % 2 == 0) ? steps : -1;
}

int main() {
   string s = "NNSE";
   int x = 2, y = 2;
   int res = minSteps(s, x, y);
   if(res == -1) cout << "Destination cannot be reached\n";
   else cout << "Minimum steps to reach destination: " << res << "\n";
   return 0;
}

輸出

Destination cannot be reached

上述程式碼接受一個表示方向的字串s和起始點（x，y）作為輸入。我們先將目前點（curr_x，curr_y）初始化為（0，0），將到達目前點的步數（steps）初始化為0。然後我們創建一個無序映射來追蹤訪問過的點。我們遍歷字串s，並根據當前字元給出的方向更新當前點和到達該點所需的步數。我們檢查當前點是否已被存取過。如果是，則跳過它。否則，我們將其標記為已訪問，並增加到達當前點的步數。

遍歷字串後，我們計算目標點和目前點之間的距離。如果目標點與目前點之間的距離小於或等於所走的步數，且所走的步數與距離之差為偶數，則傳回所走的步數作為最小步數到達目的地所需的步驟。否則，我們返回-1，表示無法到達目的地。

測試案例範例

讓我們考慮一個範例測試案例來了解上述程式碼的工作原理 -

輸入

string s = "NNSE";
int x = 2, y = 2;

在範例測試案例中，起始點為（0,0），方向為「NNSE」。目標點為（2,2）。然而，如果按照給定的方向前進，我們只會到達點（0,2），而不是目標點。因此，依照給定的方向無法到達目標點（2,2）。

結論

在本文中，我們討論瞭如何根據一系列方向最小化從給定來源到達目的地所需的步驟數。我們使用 BFS 遍歷在 C 中實作了該解決方案，並提供了一個範例來說明程式碼的工作原理。透過遵循本文討論的方法，您可以有效地解決 C 中的類似問題。

以上是最小化透過給定源點到達目的地所需的字串定義的步驟的詳細內容。更多資訊請關注PHP中文網其他相關文章！