代码随想录算法训练营第五十三天 | 图论part04

思路是要将字符串之间用线连起来，每个相邻的字符串只有一个字符不同。通过bfs来找到最短路径。要注意已经走过的路径要记录下来，包括走过的步数。
但是这一题并没有建图，而是将这个过程简化了，只是记录下了path。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>using namespace std;int main() {int n;string beginStr, endStr, str;unordered_set<string> strSet;unordered_map<string, int> visitMap;queue<string> que;cin >> n;cin >> beginStr >> endStr;while (n--) {cin >> str;strSet.insert(str);}que.push(beginStr);visitMap.insert({beginStr, 1});while (!que.empty()) {string word = que.front();que.pop();int path = visitMap[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 << endl;return 0;}if (strSet.count(newWord) == 0) continue;if (visitMap.find(newWord) == visitMap.end()) {visitMap.insert({newWord, path + 1});que.push(newWord);}}}}cout << 0 << endl;return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>
#include <list>using namespace std;void dfs(const vector<list<int>> &graph, unordered_set<int> &visited, int node) {if (visited.count(node) != 0) return;visited.insert(node);for (int n : graph[node]) {dfs(graph, visited, n);}
}int main() {int n, m, node1, node2;cin >> n >> m;vector<list<int>> graph(n + 1);while (m--) {cin >> node1 >> node2;graph[node1].push_back(node2);}unordered_set<int> visited;dfs(graph, visited, 1);if (visited.size() == n) cout << 1;else cout << -1;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 sum = 0, cover = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 1) {sum++;if (i-1 >=0 && grid[i-1][j] == 1) cover++;if (j-1 >=0 && grid[i][j-1] == 1) cover++;}}}cout << sum*4-cover*2;
}