110.字符串接龙
bfs: 求最短路径长度
# bfs
from collections import deque
from collections import defaultdict
def bfs(beginStr, endStr, strDict):que = deque()que.append(beginStr)strDict[beginStr] = 1while que:curStr = que.popleft()curList = list(curStr)for i in range(len(curStr)):for j in range(26):newChar = chr(j + ord('a'))newStr = "".join(curList[:i]) + newChar + "".join(curList[i+1:])if newStr == endStr:return strDict[curStr] + 1if newStr in strDict and strDict[newStr] == 0:que.append(newStr)strDict[newStr] = strDict[curStr] + 1# print(f"{newStr} {strDict[newStr]}")return 0if __name__ == "__main__":# inputn = int(input())beginStr, endStr = input().split()strDict = defaultdict(int)for _ in range(n):strDict[input()] = 0result = bfs(beginStr, endStr, strDict)print(result)105.有向图的完全可达性
dfs
#include <iostream>
#include <vector>
#include <list>
using namespace std;void dfs(vector<list<int>>& graph, int key, vector<bool>& visited) {//deal with this keyif (visited[key]) {return;}visited[key] = true;list<int> keys = graph[key];for (int key : keys) {dfs(graph, key, visited);}}int main()
{int n, k, s, t;cin >> n >> k;vector<list<int>> graph(n+1);while (k--) {cin >> s >> t;graph[s].push_back(t);}vector<bool> visited(n + 1, false);dfs(graph, 1, visited);for (int i = 1; i <= n; i++) {if (visited[i] == false) {cout << -1 << endl;return 0;}}cout << 1 << endl;
}#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;void bfs(vector<list<int>>& graph, int key, vector<bool>& visited) {queue<int> que;que.push(key);visited[key] = true;while (!que.empty()) {int cur = que.front();que.pop();list<int> keys = graph[cur];for (int key : keys) {if (!visited[key]) {//注意这里，不然会进入死循环que.push(key);visited[key] = true;}}}
}int main()
{int n, k, s, t;cin >> n >> k;vector<list<int>> graph(n+1);while (k--) {cin >> s >> t;graph[s].push_back(t);}vector<bool> visited(n + 1, false);bfs(graph, 1, visited);for (int i = 1; i <= n; i++) {if (visited[i] == false) {cout << -1 << endl;return 0;}}cout << 1 << endl;
}
106.岛屿的周长
dfs练手
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int directions[4][2] = { 1,0,0,1,-1,0,0,-1 };
int result = 0;void dfs(vector<vector<int>>& graph, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] || graph[x][y] == 0) {return;}visited[x][y] = true;// get circlefor (int i = 0; i < 4; i++) {int next_x = x + directions[i][0];int next_y = y + directions[i][1];if (next_x < 0 || next_x >= graph.size()) {result++;// cout << result << endl;}if (next_y < 0 || next_y >= graph[0].size()) {result++;}if (next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size()) {continue;}if (graph[next_x][next_y] == 0) {result++;//cout << result << endl;}dfs(graph, visited, next_x, next_y);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> graph[i][j];}}// int n = 5;// int m = 5;// vector<vector<int>> graph(n, vector<int>(n, 0));// graph = {// {0,0,0,0,0},// {0,1,0,1,0},// {0,1,1,1,0},// {0,1,1,1,0},// {0,0,0,0,0}// };vector<vector<bool>> visited(n, vector<bool>(m, false));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (graph[i][j] == 1) {dfs(graph, visited, i, j);}}}cout << result << endl;return 0;}也可以不用dfs
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int directions[4][2] = { 1,0,0,1,-1,0,0,-1 };int main() {int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> graph[i][j];}}// int n = 5;// int m = 5;// vector<vector<int>> graph(n, vector<int>(m, 0));// graph = {// {0,0,0,0,0},// {0,1,0,1,0},// {0,1,1,1,0},// {0,1,1,1,0},// {0,0,0,0,0}// };int result = 0;vector<vector<bool>> visited(n, vector<bool>(m, false));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// cout << i << j << endl;if (graph[i][j] == 1) {for (int k = 0; k < 4; k++) {int next_x = i + directions[k][0];int next_y = j + directions[k][1];if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m || graph[next_x][next_y] == 0) {result++;}}}}}cout << result << endl;return 0;
}
