U5-4-BFS1

原题链接：67324.4.0U5笔记合集

1943

2025-09-06 16:39:39

发布于：江苏

0阅读

0回复

0点赞

$一、队列练习$

#include <bits/stdc++.h>
#include <queue>

using namespace std;
int n,m,k; 
queue<int> q1, q2; 	//队列 

int main(){
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++) q1.push(i);
	for(int i=1; i<=m; i++) q2.push(i);
	
	for (int i=1; i<=k; i++){
		printf("%d %d\n", q1.front(), q2.front());
		q1.push(q1.front());
		q2.push(q2.front());
		q1.pop();
		q2.pop();
	}
	
	return 0;
}

$二、抓住那头牛$

#include <bits/stdc++.h>
#include <queue>
using namespace std;

queue<int> q;
int n, r; 
int d[100005];	//距离数组

int main(){
	cin >> n >> r;
	memset(d, -1, sizeof(d));	//将数组初始化为 -1 
	d[n] = 0; 
	q.push(n);	//起点加入队列
	
	while (q.size()) {
		int t = q.front();
		q.pop();
		if (r == t){		//找到牛的位置 
			cout << d[t];
			return 0; 
		}
		if (t-1>=1 && d[t-1] == -1){	//-1表示未走过 
			d[t-1] = d[t] + 1; 
			q.push(t-1);
		} 
		if (t+1<=100000 && d[t+1] == -1){
			d[t+1] = d[t] + 1;
			q.push(t+1); 
		} 
		
		if (2*t<=100000 && d[2*t] == -1){
			d[2*t] = d[t] + 1;
			q.push(2*t);
		}
	}
	return 0;
}


/*
Depth First Search 
Breadth First Search
*/

$三、迷宫最短路$

#include <bits/stdc++.h>
using namespace std;

struct node {
	int x, y, steps;
};

queue<node> q;
char mp[1005][1005];
bool vis[1005][1005];
int n, m;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

void bfs()
{
	q.push({1,1,0}); 	//第一个点入队
	vis[1][1] = 1;
	while (q.size()) {	//一直 
		//先拿出来第一个搜索点的(当前搜索的点) 队首
		node t = q.front();
		q.pop();
		//搜索的出口
		if (t.x == n && t.y == m) {
			cout << t.steps;
			return ;
		}
		//开始四个方向的搜索
		for (int i=0; i<4; i++) {
			int a = t.x + dir[i][0];
			int b = t.y + dir[i][1];
			if (a<1 || a>n || b<1 || b>m)  continue;
			if (vis[a][b]==1 || mp[a][b] == '#')  continue;
			vis[a][b] = 1;
			q.push({a, b, t.steps+1});
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin >> mp[i][j];
		}
	}
	bfs();

	return 0;
}


/*
5 5
..###
#....
#.#.#
#.#.#
#.#..

8
*/