day54|110.字符串接龙, 105.有向图的完全可达性, 106.岛屿的周长

110.字符串接龙

110. 字符串接龙 (kamacoder.com)

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<string>
#include<queue>using namespace std;int main(){int n = 0;cin >> n;string beginStr, endStr, strMid;cin >> beginStr >> endStr;unordered_set<string> strList;for(int i = 0; i < n; i++){cin >> strMid;strList.insert(strMid);}unordered_map<string, int> strMap;  // 访问到字符串str1时的长度queue<string> strQue;strQue.push(beginStr);strMap[beginStr] = 1;while(!strQue.empty()){string strFront = strQue.front();strQue.pop();int strSize = strFront.size();for(int i = 0; i < strSize; i++){string prevStr = strFront;for(int j = 0; j < 26; j++){strFront[i] = j + 'a';if(strFront == endStr){cout << strMap[prevStr] + 1 << endl;return 0;}if(strList.count(strFront) && !strMap.count(strFront)){  // 要求有且没被用过，可以保证每次到str的长度是最短的strMap[strFront] = strMap[prevStr] + 1; strQue.push(strFront);}}strFront = prevStr;}}cout << 0;return 0;}

105.有向图的完全可达性

105. 有向图的完全可达性 (kamacoder.com)

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>using namespace std;int main()
{int n = 0, k = 0;cin >> n >> k;vector<queue<int>> map(n + 1);for (int i = 0; i < k; i++){int start = 0, end = 0;cin >> start >> end;map[start].push(end);}unordered_set<int> record;queue<int> que;que.push(1);record.insert(1);while (!que.empty()){int curTop = que.front();que.pop();while (!map[curTop].empty()){int queTop = map[curTop].front();map[curTop].pop();if (record.count(queTop))  // 去重{continue;}record.insert(queTop);que.push(queTop);}}for (int i = 2; i <= n; i++){if (!record.count(i)){cout << -1 << endl;return 0;}}cout << 1 << endl;return 0;
}

106.岛屿的周长

106. 岛屿的周长 (kamacoder.com)

#include<iostream>
#include<vector>using namespace std;
int ans = 0; // 记录周长
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};void dfs(int x, int y, vector<vector<int>> &visited, vector<vector<int>> &island, int n, int m){visited[x][y] = 1;for(int i = 0; i < 4; i++){int nextX = x + dir[i][0];int nextY = y + dir[i][1];if(nextY < 0 || nextX < 0 || nextY >= m || nextX >= n || island[nextX][nextY] == 0){ans++;continue;}if(visited[nextX][nextY] == 0){dfs(nextX, nextY, visited, island, n, m);}}
}int main(){int n = 0, m = 0;cin >> n >> m;vector<vector<int>> island(n, vector<int>(m));vector<vector<int>> visited(n, vector<int>(m));for(int i = 0;i < n; i++){for(int j = 0; j < m; j++){cin >> island[i][j];}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] != 0 && visited[i][j] == 0)dfs(i, j, visited, island, n, m);}}cout << ans << endl;return 0;
}