【Weekly Algorithm】算法周记之《代码随想录》图论（二）
学习小结
本周跟随《代码随想录》继续学习关于图论的知识，主要是学习岛屿，也就是 bfs/dfs 的经典应用。同时还有[[字符串接龙]]这种新颖的图论题目，才知道各种字符串也能抽象为一个图。
图论
岛屿数量广搜版
直接说明区别和放代码好力，代码就是在[[岛屿数量深搜版]]的基础上做了一点更改，原本的搜索函数不断递归向深了探索，现在是用队列（栈也可，区别在于遍历顺序）来记录要遍历的区块，再按顺序处理
修改后的代码
plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void bfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
while (!q.empty()) {
int tmpx = q.front().first;
int tmpy = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nextx = tmpx + dir[i][0];
int nexty = tmpy + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
visited[nextx][nexty] = true;
q.push(make_pair(nextx, nexty));
// dfs(grid, visited, nextx, nexty);
}
}
}
}
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];
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
visited[i][j] = true;
result++;
bfs(grid, visited, i, j);
}
}
}
cout << result << endl;
return 0;
}岛屿的最大面积
题意：给一个二维数组，求其中纵横相连最大区块面积
方法：dfs/bfs
从零手搓代码，重点在于visited的更新要及时，这也是易忘点
第一次把visited放再递归前，少了第一块的计算，故最后会多1
下面是最后修正的正确代码plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include <iostream>
#include <vector>
using namespace std;
int result = 0;
int dr[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
void dfs(const vector<vector<int>> &grid, vector<vector<int>> &visited, int &cur_area, int x, int y) {
cur_area++;
visited[x][y] = 1;
//cout << "visiting:" << x << " " << y << endl;
for (int i = 0; i < 4; i++) {
int tmpx = x + dr[i][0];
int tmpy = y + dr[i][1];
if (tmpx < 0 || tmpx >= grid.size() || tmpy < 0 || tmpy >= grid[0].size()) continue;
if (grid[tmpx][tmpy] == 1 && visited[tmpx][tmpy] == 0) {
dfs(grid, visited, cur_area, tmpx, tmpy);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<int>> visited(grid);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cur_area = 0;
if (!(grid[i][j] == 1 && visited[i][j] == 0)) continue;
dfs(grid, visited, cur_area, i, j);
if (cur_area > result) result = cur_area;
}
}
cout << result << endl;
return 0;
}孤岛的总面积
题意：求没有与边缘相连的纵横相连区块的总面积
方法：先对边缘的岛屿用dfs/bfs，排除这些区块，然后再遍历中间的面积。
代码：
plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include <iostream>
#include <vector>
using namespace std;
int dr[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextx = x + dr[i][0];
int nexty = y + dr[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
for (int i = 0; i < n; i++) {
if (grid[i][0] == 1 && !visited[i][0]) {
dfs(grid, visited, i, 0);
}
if (grid[i][m-1] && !visited[i][m-1]) {
dfs(grid, visited, i, m-1);
}
}
for (int i = 0; i < m; i++) {
if (grid[0][i] == 1 && !visited[0][i]) {
dfs(grid, visited, 0, i);
}
if (grid[n-1][i] && !visited[n-1][i]) {
dfs(grid, visited, n-1, i);
}
}
int result = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
result++;
}
}
}
cout << result << endl;
return 0;
}沉没孤岛
题意：就是求孤岛之外的面积之和
方法：[[孤岛的总面积]]的小变式，只要在计算边缘区块时计算面积就行
代码：
plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include <iostream>
#include <vector>
using namespace std;
int dr[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextx = x + dr[i][0];
int nexty = y + dr[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
for (int i = 0; i < n; i++) {
if (grid[i][0] == 1 && !visited[i][0]) {
dfs(grid, visited, i, 0);
}
if (grid[i][m-1] && !visited[i][m-1]) {
dfs(grid, visited, i, m-1);
}
}
for (int i = 0; i < m; i++) {
if (grid[0][i] == 1 && !visited[0][i]) {
dfs(grid, visited, 0, i);
}
if (grid[n-1][i] && !visited[n-1][i]) {
dfs(grid, visited, n-1, i);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == true) {
cout << "1 ";
}
else {
cout << "0 ";
}
}
cout << endl;
}
return 0;
}水流问题
题意：给一个数组，找其中所有能够到达（左||上）&&（右||下）从高到低（同值也行）的格子
方法：普通思路是对每一个格子都做遍历，看是否能到两种边界。但是复杂度过高。反过来，从两种边界逆流遍历，再求两次遍历的交集即可获得格子
参考代码随想录思路的代码：
plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (visited[x][y]) return;
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;
if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：这里是从低向高遍历
dfs (grid, visited, nextx, nexty);
}
return;
}
int main() {
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];
}
}
// 逆流遍历,这些本质上就是visited
vector<vector<bool>> firstBoard(n, vector<bool>(m, false));
vector<vector<bool>> secondBoard(firstBoard);
// 从第一组边界和第二组边界分别逆推
for (int i = 0; i < n; i++) {
dfs(grid, firstBoard, i, 0);
dfs(grid, secondBoard, i, m-1);
}
for (int i = 0; i < m; i++) {
dfs(grid, firstBoard, 0, i);
dfs(grid, secondBoard, n-1, i);
}
// 遍历并输出最终结果
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (firstBoard[i][j] && secondBoard[i][j]) {
cout << i << " " << j << endl;
}
}
}
return 0;
}建造最大工岛
题意：给一个二维数组，沿用上面的岛屿设定，不过本题可以最多填充一块陆地，求填充完最大的陆地面积
方法：普通的暴力思路是对每块海洋求四边的陆地和；优化后，先把所有陆地给遍历，求各陆地面积，避免暴力思路中的重复遍历。
实现的重点在于，考虑全陆地的情况，并且要考虑到四边的陆地可能是同一块陆地，所以要去重。
参考代码随想录思路的解法
plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int n, m;
int dr[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y, int &count, int mark) {
// 加速返回
if (visited[x][y] || grid[x][y] == 0) return;
count++;
visited[x][y] = true;
grid[x][y] = mark;
for (int i = 0; i < 4; i++) {
int nextx = x + dr[i][0];
int nexty = y + dr[i][1];
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if (grid[nextx][nexty] == 1 && !visited[nextx][nexty]) {
dfs(grid, visited, nextx, nexty, count, mark);
}
}
}
int main() {
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];
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false));
unordered_map<int, int> gridNum;
int flagNum = 2;
bool isAllGrid = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) isAllGrid = false;
int count = 0;
if (!visited[i][j] && grid[i][j] == 1) {
dfs(grid, visited, i, j, count, flagNum);
gridNum[flagNum] = count;
//cout << "flagNum:" << flagNum << "; count:" << count << endl;
flagNum++;
}
}
}
if (isAllGrid) {
cout << n*m << endl;
return 0;
}
unordered_set<int> visitGrid;
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 0) continue;
visitGrid.clear();
int area = 1;
//cout << "出发：" << i << j << endl;
for (int k = 0; k < 4; k++) {
int nx = i + dr[k][0];
int ny = j + dr[k][1];
//cout << "查看：" << nx << ny << endl;
if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == 0) continue;
if (visitGrid.count(grid[nx][ny])) continue;
area += gridNum[grid[nx][ny]];
//cout << "发现：" << grid[nx][ny] << ";gridNum:" << gridNum[grid[nx][ny]] << ";area:" << area << endl;
visitGrid.insert(grid[nx][ny]);
}
result = max(result, area);
}
}
cout << result << endl;
return 0;
}字符串接龙
题意：给一个起始字符串和终止字符串，以及一系列字符串，求起始字符串每次更改一个字符，从这些字符串最少更改几步到终止字符串。
方法：看作从起始字符串开始的无向图，向周围bfs（bfs比dfs更方便找最短路径），也就是逐个尝试26字母。
参考代码随想录思路的解法
plaintext1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;
int main() {
string beginStr, endStr, str;
int n;
cin >> n;
unordered_set<string> strSet;
cin >> beginStr >> endStr;
for (int i = 0; i < n; i++) {
cin >> str;
strSet.insert(str);
}
// 记录字符串是否访问，以及访问到字符串的路径长度
unordered_map<string, int> visitMap;
// 为了bfs的队列
queue<string> que;
que.push(beginStr);
// 起始的长度为1
visitMap.insert(make_pair(beginStr, 1));
while(!que.empty()) {
string word = que.front();
que.pop();
int path = visitMap[word];
// 对于word逐个字符尝试替换，然后匹配strSet
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 (strSet.find(newWord) != strSet.end() &&
visitMap.find(newWord) == visitMap.end()) {
// 记录访问结果，并添加队列
visitMap.insert(make_pair(newWord, path+1));
que.push(newWord);
}
}
}
}
// 无结果
cout << 0 << endl;
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
系列文章
