【C++算法】87.BFS解決最短路徑問題_為高爾夫比賽砍樹

文章目錄

    • 題目鏈接:
    • 題目描述:
    • 解法
    • C++ 算法代碼:


題目鏈接:

675. 為高爾夫比賽砍樹


題目描述:

0339fa60c45511642b1d5d83f27bd81f


解法

注意:砍樹要從低到高砍。

砍掉1,從1到5到2

砍掉2,從2到5到3

砍掉3,從3到5到2到6到4

砍掉4,從4到6到5

砍掉5,從5到6

砍掉6

4e11a26528f702773cd0fa1559e658b7

變成若干個迷宮問題了。

把所有的最小值求出來然后加起來。

3fc2f78c65c913da061063fc9ac8c177

但是有個問題,你怎么知道砍樹的順序呢?

所以我們要先找到砍樹的順序,弄個二維數組先存一下下標和內容,然后按照內容由小到大排序。


C++ 算法代碼:

class Solution {int m, n;  // 森林的行數和列數public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 1. 準備工作:找出所有需要砍的樹,并按樹的高度排序vector<pair<int, int>> trees;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (f[i][j] > 1)  // 樹的高度大于1才需要砍trees.push_back({i, j});// 按照樹的高度從小到大排序sort(trees.begin(), trees.end(),[&](const pair<int, int>& p1, const pair<int, int>& p2) {return f[p1.first][p1.second] < f[p2.first][p2.second];});// 2. 按照順序砍樹int bx = 0, by = 0;  // 起始位置(0,0)int ret = 0;  // 總步數for (auto& [a, b] : trees) {// 計算從當前位置到下一棵樹的最短步數int step = bfs(f, bx, by, a, b);if (step == -1)  // 如果無法到達,返回-1return -1;ret += step;  // 累加步數bx = a, by = b;  // 更新當前位置}return ret;}bool vis[51][51];  // 訪問標記數組int dx[4] = {0, 0, 1, -1};  // 四個方向的x偏移量int dy[4] = {1, -1, 0, 0};  // 四個方向的y偏移量// BFS計算從起點(bx,by)到終點(ex,ey)的最短步數int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey) {if (bx == ex && by == ey)  // 如果起點就是終點,返回0步return 0;queue<pair<int, int>> q;memset(vis, 0, sizeof vis);  // 清空訪問標記q.push({bx, by});vis[bx][by] = true;int step = 0;while (q.size()) {step++;int sz = q.size();// 處理當前層的所有節點while (sz--) {auto [a, b] = q.front();q.pop();// 嘗試四個方向for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];// 檢查新位置是否合法if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] != 0 && !vis[x][y]) {  // 0表示不能走的障礙物// 找到終點,返回當前步數if (x == ex && y == ey)return step;q.push({x, y});vis[x][y] = true;}}}}return -1;  // 無法到達終點}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/91377.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/91377.shtml
英文地址,請注明出處:http://en.pswp.cn/web/91377.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

JavaScript內存管理完全指南:從入門到精通

文章目錄JavaScript內存管理完全指南&#xff1a;從入門到精通1. 哪些數據類型屬于引用類型&#xff08;復雜數據類型&#xff09;&#xff1f;2. 為什么引用類型要存儲在堆中&#xff1f;3. 引用類型的內存存儲示例示例 1&#xff1a;對象&#xff08;Object&#xff09;示例 …

Linux網絡-------3.應?層協議HTTP

1.HTTP協議 雖然我們說,應?層協議是我們程序猿??定的.但實際上,已經有?佬們定義了?些現成的,??常好?的應?層協議,供我們直接參考使?.HTTP(超?本傳輸協議)就是其中之?。 在互聯?世界中&#xff0c;HTTP&#xff08;HyperText Transfer Protocol&#xff0c;超?本…

05 GWAS表型數據處理原理

表型數據處理 ? 質量性狀 – 二分類&#xff1a;可用0 / 1, 1 / 2 數值表示 – 多分類&#xff1a;啞變量賦值&#xff0c;0/1 ? 數量性狀 – 盡量符合正太分布 – 剔除異常表型值樣本 – 多年多點重復觀測 – 對于閾值性狀&#xff0c;分級數量化或啞變量賦值 R中 shapiro.t…

【Cpolar實現內網穿透】

Cpolar實現內網穿透業務需求第一步&#xff1a;準備工作1、關閉安全軟件2、下載所需軟件第二步&#xff1a;Nginx的配置第三步&#xff1a;使用cpolar實現內網穿透1、進入 https://dashboard.cpolar.com/get-started 注冊&#xff0c;登錄&#xff0c;完成身份證的實名認證2、下…

基于 JavaWeb+MySQL 的學院黨費繳費系統

基于 JavaWeb 的學院黨費繳費系統第 1 章緒論1.1 項目背景當今互聯網發展及其迅速&#xff0c;互聯網的便利性已經遍及到各行各業&#xff0c;惠及到每一個人&#xff0c;傳統的繳費方式都需要每個人前往繳費點陸續排隊繳費&#xff0c;不僅浪費大量了個人時間&#xff0c;而且…

LCGL基本使用

LVGC簡介 light video Graphics Library (1)純c與語言編程,將面向對象的思想植入c語言。 (2)輕量化圖形庫資源,人機交互效果好,在(ios Android QT)移植性較好,但是這些平臺對硬件要求較高 lcgc工程搭建 工程源碼的獲取 獲取工程結構 https://github.com/lvgl/lv_po…

嵌入式第十六課!!!結構體與共用體

一、結構體結構體是一種數據類型&#xff0c;它的形式是這樣的&#xff1a;struct 結構體名{ 結構體成員語句1&#xff1b;結構體成員語句2&#xff1b;結構體成員語句3&#xff1b;}&#xff1b;舉個例子&#xff1a;struct Student {int id;char name[20];float score…

java web 實現簡單下載功能

java web 實現簡單下載功能 項目結構├── src\ │ ├── a.txt │ └── com\ │ └── demo\ │ └── web\ │ ├── Cookie\ │ ├── download\ │ ├── homework\ │ ├── serv…

虛幻基礎:模型穿模

能幫到你的話&#xff0c;就給個贊吧 &#x1f618; 文章目錄模型穿模模型之間的阻擋是否正確設置模型是角色的組件&#xff1a;角色的組件不會與場景中其他的物體發生阻擋但可以發生重疊模型穿模 模型之間的阻擋是否正確設置 模型是角色的組件&#xff1a;角色的組件不會與場…

【Linux】linux基礎開發工具(二) 編譯器gcc/g++、動靜態庫感性認識、自動化構建-make/Makefile

文章目錄一、gcc/g介紹二、gcc編譯選項預處理編譯匯編鏈接三個細節三、動靜態庫感性認識動靜態庫的優缺點四、自動化構建-make/Makefile背景知識初步上手Makefilemakefile的推導過程makefile語法一、gcc/g介紹 我們之前介紹了編輯器vim&#xff0c;可以讓我們在linux上linux系統…

CentOS 7 上使用 Docker 安裝 Jenkins 完整教程

目錄 前言 準備工作 系統要求 檢查系統信息 更新系統 安裝Docker 第一步:卸載舊版本Docker(如果存在) 第二步:安裝必要的軟件包 第三步:添加Docker官方倉庫 第四步:安裝Docker CE 第五步:啟動Docker服務 第六步:驗證Docker安裝 第七步:配置Docker用戶權限…

30.【.NET8 實戰--孢子記賬--從單體到微服務--轉向微服務】--單體轉微服務--公共代碼--用戶上下文會話

在前面的文章中&#xff0c;我們會看到使用ContextSession來獲取當前用戶的UserId和UserName。這篇文章我們就一起來看看如何實現ContextSession。 一、ContextSession的實現 我們在公共類庫SP.Common中創建一個名為ContextSession的類&#xff0c;用于獲取當前請求的用戶信息。…

BaseDao

#### 10.1 DAO概念> DAO&#xff1a;Data Access Object&#xff0c;數據訪問對象。 > > Java是面向對象語言&#xff0c;數據在Java中通常以對象的形式存在。一張表對應一個實體類&#xff0c;一張表的操作對應一個DAO對象&#xff01;>> 在Java操作數據庫時&a…

USRP捕獲手機/路由器數據傳輸信號波形(中)

目錄&#xff1a; USRP捕獲手機/路由器數據傳輸信號波形&#xff08;上&#xff09; USRP捕獲手機/路由器數據傳輸信號波形&#xff08;中&#xff09; USRP捕獲手機/路由器數據傳輸信號波形&#xff08;下&#xff09; 三、雙工通信信號捕獲 3.1 信號接收系統 5805e6Hz&a…

使用 Kiro AI IDE 3小時實現全棧應用Admin系統

Hello&#xff0c; 大家好&#xff0c;我是程序員海軍, 全棧開發 |AI愛好者 &#xff5c; 獨立開發。 之前我是采用Node生態開發的大模型以及MCP Server,大模型開發的生態主要是Python語言&#xff0c;為了更好的學習大模型開發&#xff0c;于是開了新坑。開始學習Python, 以及…

瀏覽器pdf、image顯示

瀏覽器地址欄 pdf data:application/pdf;base64, data:application/pdf;base64,JVBERi0xLjcKJeLjz9MKMjMgMCBvYmoKPDwv image data:image/jpeg;base64, data:image/jpeg;base64,/9j/4Q3fRXhpZgAATU0AKgAAAAgABwE

《Linux運維總結:銀河麒麟V10 SP3啟動docker容器報錯permission denied》

總結&#xff1a;整理不易&#xff0c;如果對你有幫助&#xff0c;可否點贊關注一下&#xff1f; 更多詳細內容請參考&#xff1a;Linux運維實戰總結 一、環境信息 二、背景 1、使用docker啟動一個nginx容器&#xff0c;報錯信息如下&#xff1a; docker: Error response from…

PDF源碼解析

PDF源碼解析打開PDF解析PDF?0. 文件頭關鍵信息解析技術原理圖解文件頭的重要性實際文件結構示例開發者注意事項歷史背景1. 根目錄整體結構關鍵字段解析核心概念解釋實際應用場景完整對象關系圖技術總結2. 頁面樹對象結構關鍵字段解析頁面樹工作原理技術要點總結實際應用3. 圖像…

java開閉原則 open-closed principle

基本知識 1.核心思想&#xff1a;面向抽象編程 2.基本內涵&#xff1a;對修改關閉&#xff0c;對擴展開放 3.要求&#xff1a;盡可能不修改源碼而是增加新功能 例子 以spring5核心原理與30個類手寫實戰中的為例 package com.gupaoedu.vip.design.principle.openclose;/*** Crea…

擁抱智慧物流時代:數字孿生技術的應用與前景

概述 在數字經濟全面推進的當下&#xff0c;物流行業正經歷著前所未有的智能化升級。作為新一代信息技術的重要代表&#xff0c;數字孿生技術正悄然改變著物流的運作方式和決策模式。所謂數字孿生&#xff0c;是指在虛擬空間中創建與現實物流系統高度一致的數字模型&#xff0…