算法训练营day67

题目1：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>using namespace std;int main() {string beginStr, endStr;int n;cin >> n;cin >> beginStr >> endStr;unordered_set<string> set;for(int i = 0;i < n;i++) {string str;cin >> str;set.insert(str);}unordered_map<string, int> visitedmp;visitedmp.insert(pair<string, int>(beginStr, 1));queue<string> qu;qu.push(beginStr);while(!qu.empty()) {string word = qu.front();qu.pop();int path = visitedmp[word];for(int i = 0;i < word.size();i++) {string newword = word;for(int j = 0;j < 26;j++) {newword[i] = j + 'a';if(newword == endStr) {cout << path + 1 << endl;return 0;}if(visitedmp.find(newword) == visitedmp.end() && set.find(newword) != set.end()) {visitedmp.insert(pair<string, int>(newword, path + 1));qu.push(newword);}}}}cout << 0 << endl;return 0;
}

题目2：105. 有向图的完全可达性 (kamacoder.com)

#include<bits/stdc++.h>using namespace std;int n, m;void dfs(vector<vector<int>>& map, int key, vector<bool>& visited) {if(visited[key]) {return;}visited[key] = true;for(int i = 1;i <= n;i++) {if(map[key][i] == 1) {dfs(map, i, visited);}}
}int main() {cin >> n >> m;vector<vector<int>> map(n + 1, vector<int>(n + 1, 0));while(m--) {int i,j;cin >> i >> j;map[i][j] = 1;}vector<bool> visited(n + 1, false);dfs(map, 1, visited);for(int i = 1;i <= n;i++) {if(!visited[i]) {cout << -1 << endl;return 0;}}cout << 1 << endl;return 0;
}

题目3：106. 岛屿的周长 (kamacoder.com)

// 其实可以不用dfs因为题目说了中间岛屿是联通的
#include<iostream>
#include<vector>using namespace std;
int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
int n, m;
vector<pair<int, int>> result;
int count = 0;void dfs(vector<vector<int>>& map, vector<vector<bool>>& visited, int x, int y) {if(map[x][y] == 0 || visited[x][y]) {return;}result.push_back(pair<int, int>(x, y));visited[x][y] = true;for(int i = 0;i < 4;i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;dfs(map, visited, nextx, nexty);}
}int main() {cin >> n >> m;vector<vector<int>> map(n, vector<int>(m));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {cin >> map[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));for(int i = 0;i < n;i++) {for(int j= 0;j < m;j++) {if(map[i][j] != 0 && !visited[i][j]) {dfs(map, visited, i, j);}}}for(int i = 0;i < result.size();i++) {int x = result[i].first;int y = result[i].second;for(int j = 0;j < 4;j++) {int nextx = x + dir[j][0];int nexty = y + dir[j][1];if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) {if(nextx == -1 || nextx == n || nexty == -1 || nexty == m) count++;continue;}if(map[nextx][nexty] == 0) count++;}}cout << count << endl;return 0;
}