110.字符串接龙
bfs: 求最短路径长度
# bfs
from collections import deque
from collections import defaultdict
def bfs(beginStr, endStr, strDict):
que = deque()
que.append(beginStr)
strDict[beginStr] = 1
while 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] + 1
if newStr in strDict and strDict[newStr] == 0:
que.append(newStr)
strDict[newStr] = strDict[curStr] + 1
# print(f"{newStr} {strDict[newStr]}")
return 0
if __name__ == "__main__":
# input
n = int(input())
beginStr, endStr = input().split()
strDict = defaultdict(int)
for _ in range(n):
strDict[input()] = 0
result = 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 key
if (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 circle
for (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;
}