杭電oj(1180、1181)題解

?

目錄

1180

題目

思路

問題概述

代碼思路分析

1. 數據結構與全局變量

2. BFS 函數?bfs

3. 主函數?main

總結

代碼

1181

題目

思路

1. 全局變量的定義

2. 深度優先搜索函數?dfs

3. 主函數?main

總結

代碼


?

1180

題目

思路

注:當走的方向和樓梯方向一致的時候不用等樓梯

問題概述

存在一個由字符構成的迷宮,每個字符代表不同的地形。起點用?S?表示,終點用?T?表示,障礙物用?*?表示,還有兩種特殊地形:豎杠?|?和橫杠?-,它們會依據時間(步數)的奇偶性來改變通行規則。代碼的目的是找出從起點到終點的最短步數。

代碼思路分析

1. 數據結構與全局變量
char map[25][25];
bool val[25][25];
int n,m;
int dxy[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct node{int t;int x,y;
};

  • map:二維字符數組,用于存儲迷宮地圖。
  • val:二維布爾數組,用于標記某個位置是否已經被訪問過。
  • n?和?m:分別代表迷宮的行數和列數。
  • dxy:二維數組,存儲四個方向(上、右、下、左)的偏移量,便于后續遍歷相鄰位置。
  • node:結構體,用于存儲當前位置的信息,包含時間?t?以及坐標?(x, y)
2. BFS 函數?bfs
int bfs(node temp){queue<node>q;while(!q.empty()){q.pop();}q.push(temp);while(!q.empty()){temp=q.front();q.pop();if(map[temp.x][temp.y]=='T') return temp.t;for(int i=0;i<4;i++){node next;next.x=temp.x+dxy[i][0];next.y=temp.y+dxy[i][1];next.t=temp.t+1;if(val[next.x][next.y] || map[next.x][next.y]=='*' || next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if(map[next.x][next.y]=='|'){next.x+=dxy[i][0];next.y+=dxy[i][1];if(val[next.x][next.y] || map[next.x][next.y]=='*' || next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if((temp.t%2==1 && dxy[i][1]==0) || (temp.t%2==0 && dxy[i][0]==0)) next.t++;}else if(map[next.x][next.y]=='-'){next.x+=dxy[i][0];next.y+=dxy[i][1];if(val[next.x][next.y] || map[next.x][next.y]=='*' || next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if((temp.t%2==1 && dxy[i][0]==0) || (temp.t%2==0 && dxy[i][1]==0)) next.t++;}val[next.x][next.y]=true;q.push(next);}}
}

  • 初始化一個隊列?q,并將起點加入隊列。
  • 持續從隊列中取出元素,若當前位置為終點?T,則返回當前的時間?t
  • 遍歷當前位置的四個相鄰位置:
    • 若相鄰位置已被訪問、是障礙物或者越界,則跳過。
    • 若相鄰位置是?|?或?-,需要額外處理:
      • 先跨過該位置,檢查新位置是否合法。
      • 根據當前時間的奇偶性以及移動方向,判斷是否需要額外增加時間。
    • 標記新位置為已訪問,并將其加入隊列。
3. 主函數?main
int main(){while(cin>>n>>m){node sta;memset(val, false, sizeof(val));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>map[i][j];if(map[i][j]=='S'){val[i][j]=true;sta.t=0;sta.x=i;sta.y=j;}}}cout<<bfs(sta)<<endl;}return 0;
}

  • 持續讀取迷宮的行數和列數。
  • 初始化?val?數組為?false,表示所有位置都未被訪問。
  • 讀取迷宮地圖,找到起點?S,并標記起點為已訪問。
  • 調用?bfs?函數進行搜索,并輸出最短步數。

總結

此代碼運用 BFS 算法,從起點開始逐層擴展,直至找到終點。在擴展過程中,針對特殊地形?|?和?-,依據時間的奇偶性和移動方向來決定是否需要額外增加時間,最終輸出從起點到終點的最短步數。

代碼

#include<iostream>
#include<queue> 
using namespace std;
char map[25][25];
bool val[25][25];
int n,m;
int dxy[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct node{int t;int x,y;
};int bfs(node temp){queue<node>q;while(!q.empty()){q.pop();}q.push(temp);while(!q.empty()){temp=q.front();q.pop();if(map[temp.x][temp.y]=='T') return temp.t;for(int i=0;i<4;i++){node next;next.x=temp.x+dxy[i][0];next.y=temp.y+dxy[i][1];next.t=temp.t+1;if(val[next.x][next.y] || map[next.x][next.y]=='*' || next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if(map[next.x][next.y]=='|'){next.x+=dxy[i][0];next.y+=dxy[i][1];if(val[next.x][next.y] || map[next.x][next.y]=='*' || next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if((temp.t%2==1 && dxy[i][1]==0) || (temp.t%2==0 && dxy[i][0]==0)) next.t++;}else if(map[next.x][next.y]=='-'){next.x+=dxy[i][0];next.y+=dxy[i][1];if(val[next.x][next.y] || map[next.x][next.y]=='*' || next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if((temp.t%2==1 && dxy[i][0]==0) || (temp.t%2==0 && dxy[i][1]==0)) next.t++;}val[next.x][next.y]=true;q.push(next);}}
}
int main(){while(cin>>n>>m){node sta;memset(val, false, sizeof(val));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>map[i][j];if(map[i][j]=='S'){val[i][j]=true;sta.t=0;sta.x=i;sta.y=j;}}}cout<<bfs(sta)<<endl;}return 0;
}

1181

題目

思路

核心思路:將所有滿足條件的情況放到動態數組中,如果數組為空輸出no否則輸出yes

這段 C++ 代碼的核心思路是利用深度優先搜索(DFS)算法來判斷輸入的字符串集合中是否存在以?'b'?開頭且以?'m'?結尾的字符串序列,并且序列中相鄰字符串滿足前一個字符串的最后一個字符與后一個字符串的第一個字符相同。下面為你詳細剖析代碼思路:

1. 全局變量的定義

vector<vector<string>> allSequences;
vector<string> ans;
vector<bool> val;
vector<string> arr;

  • allSequences:這是一個二維向量,用于存儲所有滿足條件(以?'b'?開頭且以?'m'?結尾,相鄰字符串首尾字符匹配)的字符串序列。
  • ans:這是一個一維向量,用于存儲當前正在搜索的字符串序列。
  • val:這是一個布爾類型的向量,其長度與輸入的字符串數量相同,用于標記每個字符串在當前搜索路徑中是否已經被使用過。
  • arr:這是一個一維向量,用于存儲所有輸入的字符串。

2. 深度優先搜索函數?dfs

void dfs(string s) {if (s[s.size() - 1] == 'm') {allSequences.push_back(ans);return;}for (int i = 0; i < arr.size(); i++) {if (s[s.size() - 1] == arr[i][0] && val[i] == false) {val[i] = true;ans.push_back(arr[i]);dfs(arr[i]);val[i] = false;ans.pop_back();}}
}

  • 終止條件:當當前字符串?s?的最后一個字符是?'m'?時,意味著找到了一個滿足條件的字符串序列,將當前的?ans?序列添加到?allSequences?中,然后返回。
  • 搜索過程
    • 遍歷?arr?中的每個字符串。
    • 檢查當前字符串?s?的最后一個字符是否等于?arr[i]?的第一個字符,并且?arr[i]?還未被使用過(即?val[i]?為?false)。
    • 如果滿足條件,將?arr[i]?標記為已使用(val[i] = true),并將其添加到?ans?序列中。
    • 遞歸調用?dfs?函數,繼續以?arr[i]?為當前字符串進行搜索。
    • 遞歸返回后,進行回溯操作,將?arr[i]?標記為未使用(val[i] = false),并從?ans?序列中移除。

3. 主函數?main

int main() {string s;while (true) {arr.clear();allSequences.clear();while (cin >> s) {if (s == "0") break;arr.push_back(s);}if (arr.empty()) break;val.assign(arr.size(), false);for (int i = 0; i < arr.size(); i++) {if (arr[i][0] == 'b') {ans.clear();ans.push_back(arr[i]);val[i] = true;dfs(arr[i]);val[i] = false;}}if(!allSequences.empty()) cout<<"Yes."<<endl;else cout<<"No."<<endl;}return 0;
}

  • 輸入處理
    • 持續讀取輸入的字符串,直到遇到?"0"?為止,將這些字符串存儲在?arr?中。
    • 如果?arr?為空,說明沒有輸入有效字符串,程序結束。
  • 初始化標記數組:將?val?數組的所有元素初始化為?false,表示所有字符串都未被使用。
  • 啟動搜索
    • 遍歷?arr?中的每個字符串,若其以?'b'?開頭,則將其作為起始字符串,清空?ans?并將該字符串添加到?ans?中,標記其為已使用,然后調用?dfs?函數開始搜索。
    • 搜索結束后,將該字符串標記為未使用,以便后續可能的其他搜索路徑使用。
  • 輸出結果
    • 如果?allSequences?不為空,說明找到了滿足條件的字符串序列,輸出?"Yes."
    • 否則,輸出?"No."

總結

該代碼通過深度優先搜索算法,從以?'b'?開頭的字符串開始,不斷嘗試尋找滿足首尾字符匹配條件且以?'m'?結尾的字符串序列,最終根據是否找到這樣的序列輸出相應的結果。

代碼

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<vector<string>> allSequences;
vector<string> ans;
vector<bool> val;
vector<string> arr;void dfs(string s) {if (s[s.size() - 1] == 'm') {allSequences.push_back(ans);return;}for (int i = 0; i < arr.size(); i++) {if (s[s.size() - 1] == arr[i][0] && val[i] == false) {val[i] = true;ans.push_back(arr[i]);dfs(arr[i]);val[i] = false;ans.pop_back();}}
}int main() {string s;while (true) {arr.clear();allSequences.clear();while (cin >> s) {if (s == "0") break;arr.push_back(s);}if (arr.empty()) break;val.assign(arr.size(), false);for (int i = 0; i < arr.size(); i++) {if (arr[i][0] == 'b') {ans.clear();ans.push_back(arr[i]);val[i] = true;dfs(arr[i]);val[i] = false;}}if(!allSequences.empty()) cout<<"Yes."<<endl;else cout<<"No."<<endl;}return 0;
}    

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

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

相關文章

軟件測試概念

這里寫目錄標題 需求開發模型軟件生命周期瀑布模型螺旋模型增量模型、迭代模型敏捷模型Scrum 測試模型V模型W模型&#xff08;雙V模型&#xff09; 需求 用戶需求&#xff1a;沒有經過合理的評估&#xff0c;通常就是一句話 軟件需求&#xff1a;是開發人員和測試人員執行工作…

數字基帶信號和頻帶信號的區別解析

數字基帶信號和數字頻帶信號是通信系統中兩種不同的信號形式&#xff0c;它們的核心區別在于是否經過調制以及適用的傳輸場景。以下是兩者的主要區別和分析&#xff1a; 1. 定義與核心區別 數字基帶信號&#xff08;Digital Baseband Signal&#xff09; 未經調制的原始數字信號…

Linux52 運行百度網盤 解決故障無法訪問repo nosandbox 未解決:疑似libstdc++版本低導致無法運行baidu網盤

昨日參考 哦 我是root Cannot find a valid baseurl for repo: centos-sclo-rh/x86_64 沒了 計劃去手動下一個 還是不行 放棄 猜測是 centos7 過期了 一些依賴組件也沒地方下載了 通過阿里云鏡像站下載 之前安裝的好像不是這個版本 還是計劃用yum去下載依賴&#xff0c;先處…

2000-2022年上市公司數字經濟專利申請數據

2000-2022年上市公司數字經濟專利申請數據 1、時間&#xff1a;2000-2022年 2、來源&#xff1a;國家知識產權局 3、指標&#xff1a;年份、股票代碼、股票簡稱、行業名稱、行業代碼、省份、城市、區縣、行政區劃代碼、城市代碼、區縣代碼、首次上市年份、上市狀態、數字經濟…

機器學習之五:基于解釋的學習

正如人們有各種各樣的學習方法一樣&#xff0c;機器學習也有多種學習方法。若按學習時所用的方法進行分類&#xff0c;則機器學習可分為機械式學習、指導式學習、示例學習、類比學習、解釋學習等。這是溫斯頓在1977年提出的一種分類方法。 有關機器學習的基本概念&#xff0c;…

Chromium 134 編譯指南 - Android 篇:安裝構建依賴項(七)

1. 引言 歡迎來到《Chromium 134 編譯指南》系列的第七篇文章&#xff01;在前面的章節中&#xff0c;我們已經成功獲取了Chromium源代碼&#xff0c;并將其配置為支持Android平臺。這些步驟為我們的編譯之旅奠定了堅實的基礎&#xff0c;但在開始實際編譯之前&#xff0c;我們…

java 進階 1.0

靜態方法 static 就是能直接用&#xff0c;不用再new一個對象了 一般java中Math等靜態類就是可以直接使用其方法 main函數里面不能包含太多的邏輯性語句&#xff0c;全部寫成模塊 寫好程序之后如何測試呢&#xff1f; 使用junit&#xff0c;不能在main函數里測試 測試本身就…

中小企業MES系統詳細設計

版本&#xff1a;V1.1 日期&#xff1a;2025年5月2日 一、設備協議兼容性設計 1.1 設備接入框架 #mermaid-svg-PkwqEMRIIlIBPP58 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-PkwqEMRIIlIBPP58 .error-icon{fill…

Spring Security會話管理

用戶認證通過后&#xff0c;為了避免用戶的每次操作都進行認證&#xff0c;可以將用戶的信息保存在會話中。會話就是系統為了保持當前用戶的登錄狀態所提供的機制&#xff0c;常見的有基于Session方式、基于Token方式等。Spring Security提供會話管理功能&#xff0c;只需要配置…

PostgreSQL數據庫操作基本命令

常用操作sql &#x1f510; 用戶管理 -- 創建用戶 CREATE USER username WITH PASSWORD password;-- 修改用戶密碼 ALTER USER username WITH PASSWORD newpassword;-- 刪除用戶 DROP USER username;&#x1f4e6; 數據庫操作 -- 創建數據庫 CREATE DATABASE dbname;-- 刪除…

[吾愛出品] 網文提取精靈_4.0

網文提取精靈 鏈接&#xff1a;https://pan.xunlei.com/s/VOPDvKljcT3EWLjpt5LeDZvfA1?pwdw8kq# 易語言寫的&#xff0c;介意的不要下載 相對網文提取工具_2.10.02版&#xff0c;因為是重寫界面&#xff0c;目前版本限制最高5線程&#xff0c;暫時不支持批處理。 雖然不支…

每日算法-250502

每日算法 - 2025.05.02 記錄一下今天刷的幾道 LeetCode 算法題。 3191. 使二進制數組全部等于 1 的最少操作次數 I 題目 思路 貪心 解題過程 遍歷數組 nums。當我們遇到 nums[i] 時&#xff1a; 如果 nums[i] 是 1&#xff0c;我們不需要進行操作&#xff0c;因為目標是全 …

移動端開發中設備、分辨率、瀏覽器兼容性問題

以下是針對移動端開發中設備、分辨率、瀏覽器兼容性問題的 系統化解決方案&#xff0c;按開發流程和技術維度拆解&#xff0c;形成可落地的執行步驟&#xff1a; 一、基礎環境適配&#xff1a;從「起點」杜絕兼容性隱患 1. Viewport 元標簽標準化 <meta name"viewpor…

2025最新AI繪畫系統源碼 - 畫圖大模型/GPT-4全支持/AI換臉/自定義智能體

在AI繪畫技術日新月異的2025年&#xff0c;比象AI繪畫系統源碼以其突破性的技術創新重新定義了數字藝術創作的邊界。作為第四代AI繪畫引擎&#xff0c;我們不僅集成了最先進的GPT-4o多模態畫圖模型&#xff0c;實現了從基礎文生圖到專業級藝術創作的全面進化。本系統源碼經過多…

構造函數詳解

構造函數的作用 構造函數的主要任務是初始化對象&#xff0c;而不是創建對象&#xff08;對象的內存空間在構造函數被調用前已經分配好&#xff09;。 構造函數特性 命名規則&#xff1a;函數名必須與類名完全相同。 返回值&#xff1a;構造函數沒有返回值類型&#xff08;連…

jaffree 封裝ffmpeg 轉換視頻格式,獲取大小,時間,封面

下載 參考網址 【收藏級教程】FFmpeg音視頻處理寶典&#xff1a;從入門到精通的50個實用技巧_ffmpeg教程-CSDN博客 配置環境變量 驗證 重啟idea開發工具 springboot maven集成 <dependency><groupId>com.github.kokorin.jaffree</groupId><artifactId&…

2505C++,wmi客戶端示例

原文 #define _WIN32_DCOM #include <iostream> using namespace std; #include <comdef.h> #include <Wbemidl.h> #pragma comment(lib, "wbemuuid.lib") int main(int argc, char **argv) {HRESULT hres;//初化COM.hres CoInitializeEx(0, CO…

[面試]SoC驗證工程師面試常見問題(三)

SoC驗證工程師面試常見問題(三) 在 SoC 驗證工程師的面試中,面試官可能會要求候選人現場編寫 SystemVerilog、UVM (Universal Verification Methodology) 或 SystemC 代碼,以評估其編程能力、語言掌握程度以及解決實際驗證問題的能力。這種隨機抽題寫代碼的環節通常…

HTML5+JavaScript實現連連看游戲之二

HTML5JavaScript實現連連看游戲之二 以前一篇&#xff0c;見 https://blog.csdn.net/cnds123/article/details/144220548 連連看游戲連接規則&#xff1a; 只能連接相同圖案&#xff08;或圖標、字符&#xff09;的方塊。 連線路徑必須是由直線段組成的&#xff0c;最多可以有…

《深入淺出Git:從版本控制原理到高效協作實戰》?

Git的原理和使用 1、Git初識與安裝2、Git基本操作2.1、創建Git本地倉庫2.2、配置Git2.3、認識工作區、暫存區、版本庫2.4、修改文件2.5、版本回退2.6、撤銷修改2.7、刪除文件 3、Git分支管理3.1、理解分支3.2、創建、切換、合并分支3.3、刪除分支3.4、合并沖突3.5、合并模式3.6…