X02-Day06&Day07-代码笔记
2024-08-09 17:24:19
发布于:北京
Day06-深度优先搜索
#include<bits/stdc++.h>
using namespace std;
const int N=50;
char mp[N][N];//map
int vis[N][N];//已走过位置的标记数组
int n,m;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
void Print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<vis[i][j];
}cout<<endl;
}
cout<<"=====分界线====\n";
}
bool ok=false;//若能到达(n,m),那么就是true
void dfs(int x,int y){
if(ok)return ;
if(x==n&&y==m){
ok=true;
return ;
}
//准备尝试四个方向
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
//越界判断
if(tx<1||tx>n||ty<1||ty>m)continue;
//不可走判断
if(mp[tx][ty]=='#')continue;
//已走判断
if(vis[tx][ty]==1)continue;
vis[tx][ty]=1;//这一步,就能踩下去了
// Print();
// getchar();//按回车会执行一步
dfs(tx,ty);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
//准备从(1,1)->(n,m);
vis[1][1]=1;
dfs(1,1);
if(ok)cout<<"YES";
else cout<<"NO";
return 0;
}
供复习练习题
应用:
Day07-广度优先搜索
// 一石激起千层浪
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 110;
struct Node {
int x, y;
int step;
};
int vis[N][N];
int n, m; // 池塘的尺寸
int s, e; // 落点
/*
-1, -1 -1, 0 -1, +1
0, -1 x, y 0, +1
+1, -1 +1, 0 +1, +1
*/
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
queue<Node> q;
void bfs() {
vis[s][e] = 1; // 将源点标记 (落点标记)
q.push(Node{s, e, 1}); // 将源点入队列 (落点入队列)
while (!q.empty()) {
Node tmp = q.front(); // 取出一个源点,准备扩散
q.pop(); // 反正都存到 tmp ,剔除
for (int i = 0; i < 8; i ++) {
int tx = tmp.x + dx[i];
int ty = tmp.y + dy[i];
// 越界判断
if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
// 是否已经被标记
if (vis[tx][ty] > 0) continue;
vis[tx][ty] = tmp.step + 1; // (tx,ty) 从 tmp 走来
q.push(Node{tx, ty, tmp.step + 1}); // (tx, ty) 将成为
// 新的扩散源
}
}
}
int main() {
cin >> n >> m;
cin >> s >> e;
bfs();
int ans = -1;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cout << vis[i][j] - 1 << " ";
ans = max(ans, vis[i][j] - 1);
}
cout << endl;
}
cout << ans << endl;
return 0;
}
供复习练习题:
准备工作
1, 定义结构体 struct Node
2,方向数组(8个方向)
3, 定义尺寸 n,m
4, 定义落点 x,y
5, 定义标记数组
6, 定义队列 (Node)
主要程序
1, 输入 n, m, x, y (知道尺寸,落点)
2, 跑图,广搜,扩散
bfs:
2.1 让落点,进入队列
2.2 只要队列中,还有扩散源点,就一直扩散
2.3 取出一个源点,并记录,并从队列中删除
2.4 从源点开始,8个方向的遍历扩散试探
能扩散的,进入队列,并标记
不能扩散的,就跳过
红与黑
1. 输入地图
2. 找到起点
当输入为 '@' ,就是起点,记录
s = i
e = j
3. 从起点开始,进行扩散(BFS)
3.1 将起点入队列
q.push({s, e, 1}); 从 1 开始走
3.2 只要队列不为空,就一直扩散
while (!q.empty()) {
3.2.1 取出队列中的一个点
3.2.2 剔除这个点
q.pop();
cnt ++;
3.2.3 从这个点开始,按要求,四周扩散
3.2.4 若能扩散,则被扩散的源点,再入队列
}
4. 输出计数 cnt
练习:
Day08👉: https://www.acgo.cn/discuss/study/24736
这里空空如也
有帮助,赞一个