文章目录
在学习数据结构课程的时候，也曾经学习过BFS和DFS，但是没有应用到实际题目中
1 广度优先搜索（BFS）
1.1 入门视频（真的很有用哟~）
1.2 题目实战（简单题，找感觉）
1.2.1 洛谷P1451
这个题目真的，刚开始没弄懂题意，不知道它的细胞是怎么算的。花费了不少时间，当搞清楚这一点之后，直接按照BFS的思路即可码出答案
- 看看这个样例：
4 10
0234500067
1034560500
2045600671
0000000089
- 它是这样算一共有4个
下面是AC代码：
#include <iostream>
#include <queue>
using namespace std;
#define N 105
int a[N][N];
bool visite[N][N];
// 右下左上
int dir[4][2] = {
{
0, 1}, {
1, 0}, {
0, -1}, {
-1, 0}};
struct Point {
int x;
int y;
};
void bfs(int x, int y) {
queue<Point> q;
Point p = {
x, y};
q.push(p);
while (!q.empty()) {
Point top = q.front();
for (int k = 0; k < 4; k++) {
int next_x = top.x + dir[k][0];
int next_y = top.y + dir[k][1];
if (a[next_x][next_y] && !(visite[next_x][next_y])) {
visite[next_x][next_y] = true;
Point tmp;
tmp.x = next_x;
tmp.y = next_y;
q.push(tmp);
}
}
q.pop();
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
a[i][j] = ch - '0';
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] && (!visite[i][j])) {
bfs(i, j);
ans ++;
}
}
}
cout << ans;
return 0;
}
1.2.2 洛谷P1162
没什么好说的，直接贴代码
#include <iostream>
#include <queue>
using namespace std;
#define N 35
int a[N][N];
bool visite[N][N];
// 右下左上
int dir[4][2] = {
{
0, 1}, {
1, 0}, {
0, -1}, {
-1, 0}};
struct Point{
int x, y;
};
void bfs(int x, int y) {
a[x][y] = 2;
queue<Point> q;
Point p = {
x, y};
q.push(p);
while (!q.empty()) {
Point top = q.front();
for (int k = 0; k < 4; k++) {
int next_x = top.x + dir[k][0];
int next_y = top.y + dir[k][1];
if ((!a[next_x][next_y]) && (!visite[next_x][next_y])) {
a[next_x][next_y] = 2;
visite[next_x][next_y] = true;
Point tmp = {
next_x, next_y};
q.push(tmp);
}
}
q.pop();
}
}
int main() {
int n;
cin >> n;
Point flag;
bool isFirst = true;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) {
cin >> a[i][j];
if (a[i - 1][j] && a[i][j - 1] && isFirst && a[i][j] == 0) {
isFirst = false;
flag = {
i, j};
}
}
bfs(flag.x, flag.y);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
2 深度优先搜索（DFS）
2.1 学习视频
该视频主要学习深度优先搜索在“迷宫问题”中的应用，感觉UP主的代码还可以继续优化，但是很时候学习这种思想。
2.2 题目实战（简单题，找感觉）
2.1.1 洛谷CF629A
好吧，是CF的题目，不过我在洛谷提交的
大水题咯（增长信心还是不错的）
我是根据DFS关键词搜索的题目，刚开始没太看明白，但是仔细想过后发现，确实就是使用了DFS的思想，一条路走到黑，大概思路是：
- 从左往右，从上到下遍历搜索答案；
- 没遇到一个"C"，就开始向右寻找所有的C，再向下寻找所有的C，这样刚好不重不漏！
下面是代码：
#include <iostream>
using namespace std;
#define N 105
char c[N][N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> c[i][j];
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (c[i][j] == 'C') {
// 先找右边
for (int k = j + 1; k <= n; k ++) {
if (c[i][k] == 'C') ans++;
}
for (int k = i + 1; k <= n; k ++) {
if (c[k][j] == 'C') ans++;
}
}
}
}
cout << ans;
return 0;
}
2.2.2 洛谷CF6A
也是CF的
思路：
- 很简单的一个题目，直接取巧一下，将数据排序后判断更为简单
- 直接根据三边关系判断即可。（感觉可能是数据不够强，没有判断“任意两边之差小于第三边”）
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int aa[4];
bool isTriangle() {
return aa[0] + aa[1] > aa[2] || aa[1] + aa[2] > aa[3];
}
bool isSegment() {
return aa[0] + aa[1] >= aa[2] || aa[1] + aa[2] >= aa[3];
}
int main() {
for (int i = 0; i < 4; i++) cin >> aa[i];
sort(aa, aa + 4);
if (isTriangle()) cout << "TRIANGLE";
else if(isSegment()) cout << "SEGMENT";
else cout << "IMPOSSIBLE";
return 0;
}