本文主要是介绍代码随想录day53 110. 字符串接龙 105.有向图的完全可达性 106. 岛屿的周长,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录day53 110. 字符串接龙 105.有向图的完全可达性 106. 岛屿的周长
110. 字符串接龙
代码随想录
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>using namespace std;int main() {int N;cin >> N;string beginStr, endStr, str;cin >> beginStr >> endStr;unordered_set<string> strSet;for (int i = 0; i < N; i++) {cin >> str;strSet.insert(str);}unordered_map<string, int> pathMap;pathMap[beginStr] = 1;queue<string> que;que.push(beginStr);while (!que.empty()) {string word = que.front();que.pop();int path = pathMap[word];for (int i = 0; i < word.size(); i++) {string newWord = word;for (int j = 0; j < 26; j++) {newWord[i] = 'a' + j ;if (newWord == endStr) {cout << path + 1;return 0;}if (strSet.count(newWord) != 0 && pathMap.find(newWord) == pathMap.end()) {pathMap[newWord] = path + 1;que.push(newWord);}}}}cout << 0;return 0;
}
105.有向图的完全可达性
代码随想录
#include <vector>
#include <iostream>
#include <list>
using namespace std;void dfs(vector<list<int>> &graph, vector<bool> &visted, int begin) {visted[begin] = true;list<int> destList = graph[begin];for (int ele : destList) {if (!visted[ele]) {dfs(graph, visted, ele);}}
}int main() {int N, K, s, t;cin >> N >> K;vector<list<int>> graph(N + 1, list<int>());for (int i = 0; i < K; i++) {cin >> s >> t;graph[s].push_back(t);}vector<bool> visted(N + 1, false);dfs(graph, visted, 1);for (int i = 1; i <= N; i++) {if (!visted[i]) {cout << -1;return 0;}}cout << 1;return 0;
}
106. 岛屿的周长
代码随想录
#include <vector>
#include <iostream>using namespace std;int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int dfs(vector<vector<int>> &graph, vector<vector<bool>> &visted, int row, int col) {visted[row][col] = true;int count = 0;for (int i = 0; i < 4; i++) {int nextRow = row + dir[i][0];int nextCol = col + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size() || graph[nextRow][nextCol] == 0) {count++;continue;}if (!visted[nextRow][nextCol]) {count += dfs(graph, visted, nextRow, nextCol);}}return count;
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));vector<vector<bool>> visted(N, vector<bool>(M, false));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 1) {cout << dfs(graph, visted, i, j);return 0;}}}return 0;
}
#include <iostream>
#include <vector>
using namespace std;
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 direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};int result = 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 x = i + direction[k][0];int y = j + direction[k][1]; // 计算周边坐标x,yif (x < 0 // x在边界上|| x >= grid.size() // x在边界上|| y < 0 // y在边界上|| y >= grid[0].size() // y在边界上|| grid[x][y] == 0) { // x,y位置是水域result++;}}}}}cout << result << endl;}
这篇关于代码随想录day53 110. 字符串接龙 105.有向图的完全可达性 106. 岛屿的周长的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!