110.字符串接龍
題目鏈接：110. 字符串接龍文章講解：代碼隨想錄
?思路：
把每個字符串看成圖的一個節點。
轉換為求無權圖兩節點的的最短路徑。求最短路徑用bfs
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
unordered_map<int, int>mymap;bool canTransform(string a, string b) {int count = 0;if (a.size() != b.size())return false;int size = min(a.size(), b.size());for (int i = 0; i < size; i++) {if (a[i] != b[i])count++;}if (count == 1)return true;else return false;
}//廣搜求最短路徑
int bfs(vector<vector<bool>>graph, int begin, int end) {queue<int>mq;mq.push(begin);while (!mq.empty()) {int curStr = mq.front();if (curStr == end) { return mymap[end]; }mq.pop();for (int i = 0; i < graph.size(); i++) {if (graph[curStr][i] == true && !mymap.count(i)) {//mymap.count(i)防止走回頭路mymap[i] = mymap[curStr] + 1;mq.push(i);}}}return 0;
}int main() {//數據讀取mymap[0] = 1; //初始化不能在全局領域初始化int n;string beginStr, endStr;cin >> n;cin >> beginStr >> endStr;vector<string>strList;strList.push_back(beginStr);int size = n; //使用while（n--）會改變n的值while (size--) {string str;cin >> str;strList.push_back(str);}strList.push_back(endStr);//構造圖vector<vector<bool>>graph(n + 2, vector<bool>(n + 2, false));for (int i = 0; i < graph.size(); i++) {for (int j = 0; j < graph.size(); j++) {if (canTransform(strList[i], strList[j]))graph[i][j] = true;}}int ans = 0;ans = bfs(graph, 0, n + 1);cout << ans;
}105.有向圖的完全可達性
題目鏈接：105. 有向圖的完全聯通
文章講解：代碼隨想錄
思路：
用深搜
逐漸遍歷看第一個節點能不能到達其他節點
錯誤深搜：
#include <iostream>
#include <vector>
using namespace std;bool dfs(vector<pair<int, int>>graph, int begin, int end) {if (begin == end)return true;for (int i = 0; i < graph.size(); i++) {int first = graph[i].first;int second = graph[i].second;if (first == begin) {if (dfs(graph, second, end))break;}}return false;
}int main() {int n, k;cin >> n >> k;vector<pair<int, int>>graph;for (int i = 0; i < k; i++) {int s, t;cin >> s >> t;graph.push_back({ s,t });}int ans = 1;for (int i = 2; i <= n; i++) {if (!dfs(graph, 1, i)) { ans = -1; }}cout << ans;}錯誤原因：
沒有visited記錄已經訪問過的節點 ，導致陷入死循環。
#include <iostream>
#include <vector>
using namespace std;bool dfs(vector<pair<int, int>>graph,vector<bool>&visited, int begin, int end) {visited[begin]=true; //visited記錄已經訪問過的節點if (begin == end)return true;for (int i = 0; i < graph.size(); i++) {int first = graph[i].first;int second = graph[i].second;if (first == begin&&visited[second]==false) {if(dfs(graph,visited, second, end))return true;}}return false;
}int main() {int n, k;cin >> n >> k;vector<pair<int, int>>graph;for (int i = 0; i < k; i++) {int s, t;cin >> s >> t;graph.push_back({ s,t });}int ans = 1;for (int i = 2; i <= n; i++) {vector<bool>visited(n,false);if (!dfs(graph, visited,1, i)) { ans = -1; }}cout << ans;}106.島嶼的周長
題目鏈接：106. 島嶼的周長
文章講解：代碼隨想錄
思路：
遍歷所有陸地，統計其四個方向 如果是海 則邊數+1
不要用慣性思維用深搜
?
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int main(){ int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}int ans=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){for(int k=0;k<4;k++){int nextx=i+dir[k][0];int nexty=j+dir[k][1];if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size()){ans+=1;continue;}if(grid[nextx][nexty]==0)ans++;}}}}cout<<ans;
}
?
)
