?
目錄
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;
}