目錄
問題陳述
方法
範例
輸出
測試案例範例
結論
首頁 後端開發 C++ 最小化透過給定源點到達目的地所需的字串定義的步驟

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

Sep 07, 2023 am 08:45 AM
最小化路徑 來源到目標 字串步驟

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

最小化由給定來源到達目的地所需的字串定義的步驟是電腦科學中的常見問題。它涉及根據一系列方向找到從起點到目的地點的最短路徑。在本文中,我們將討論如何用 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中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1664
14
CakePHP 教程
1423
52
Laravel 教程
1321
25
PHP教程
1269
29
C# 教程
1249
24
C#與C:歷史,進化和未來前景 C#與C:歷史,進化和未來前景 Apr 19, 2025 am 12:07 AM

C#和C 的歷史與演變各有特色,未來前景也不同。 1.C 由BjarneStroustrup在1983年發明,旨在將面向對象編程引入C語言,其演變歷程包括多次標準化,如C 11引入auto關鍵字和lambda表達式,C 20引入概念和協程,未來將專注於性能和系統級編程。 2.C#由微軟在2000年發布,結合C 和Java的優點,其演變注重簡潔性和生產力,如C#2.0引入泛型,C#5.0引入異步編程,未來將專注於開發者的生產力和雲計算。

C#vs. C:學習曲線和開發人員的經驗 C#vs. C:學習曲線和開發人員的經驗 Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显著差异。1)C#的学习曲线较平缓,适合快速开发和企业级应用。2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

C社區:資源,支持和發展 C社區:資源,支持和發展 Apr 13, 2025 am 12:01 AM

C 學習者和開發者可以從StackOverflow、Reddit的r/cpp社區、Coursera和edX的課程、GitHub上的開源項目、專業諮詢服務以及CppCon等會議中獲得資源和支持。 1.StackOverflow提供技術問題的解答;2.Reddit的r/cpp社區分享最新資訊;3.Coursera和edX提供正式的C 課程;4.GitHub上的開源項目如LLVM和Boost提陞技能;5.專業諮詢服務如JetBrains和Perforce提供技術支持;6.CppCon等會議有助於職業

C和XML:探索關係和支持 C和XML:探索關係和支持 Apr 21, 2025 am 12:02 AM

C 通過第三方庫(如TinyXML、Pugixml、Xerces-C )與XML交互。 1)使用庫解析XML文件,將其轉換為C 可處理的數據結構。 2)生成XML時,將C 數據結構轉換為XML格式。 3)在實際應用中,XML常用於配置文件和數據交換,提升開發效率。

超越炒作:評估當今C的相關性 超越炒作:評估當今C的相關性 Apr 14, 2025 am 12:01 AM

C 在現代編程中仍然具有重要相關性。 1)高性能和硬件直接操作能力使其在遊戲開發、嵌入式系統和高性能計算等領域佔據首選地位。 2)豐富的編程範式和現代特性如智能指針和模板編程增強了其靈活性和效率,儘管學習曲線陡峭,但其強大功能使其在今天的編程生態中依然重要。

C的未來:改編和創新 C的未來:改編和創新 Apr 27, 2025 am 12:25 AM

C 的未來將專注於並行計算、安全性、模塊化和AI/機器學習領域:1)並行計算將通過協程等特性得到增強;2)安全性將通過更嚴格的類型檢查和內存管理機制提升;3)模塊化將簡化代碼組織和編譯;4)AI和機器學習將促使C 適應新需求,如數值計算和GPU編程支持。

C  中的chrono庫如何使用? C 中的chrono庫如何使用? Apr 28, 2025 pm 10:18 PM

使用C 中的chrono庫可以讓你更加精確地控制時間和時間間隔,讓我們來探討一下這個庫的魅力所在吧。 C 的chrono庫是標準庫的一部分,它提供了一種現代化的方式來處理時間和時間間隔。對於那些曾經飽受time.h和ctime折磨的程序員來說,chrono無疑是一個福音。它不僅提高了代碼的可讀性和可維護性,還提供了更高的精度和靈活性。讓我們從基礎開始,chrono庫主要包括以下幾個關鍵組件:std::chrono::system_clock:表示系統時鐘,用於獲取當前時間。 std::chron

C:死亡還是簡單地發展? C:死亡還是簡單地發展? Apr 24, 2025 am 12:13 AM

1)c relevantduetoItsAverity and效率和效果臨界。 2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

See all articles