0%

bfs

发表于 2024-09-13 更新于 2024-09-21 阅读次数： Valine：

广度优先算法

COGS3008 朋友圈

NOI班有n位学员，因为相处时间有限，有的学员之间加了微信，有的学员之间没有。假设加微信的关系是相互的，即如果a加了b的微信，b也会加a的微信。

现在有一条NOI班上的爆炸性的新闻从1号学员发出，每个看到这个新闻的NOI班学员都会在朋友圈转发，而加了他微信的朋友都会看到。没有在NOI班上的学员都不会转发（因为和自己关系不大）。

告诉你NOI班上的学员之间的微信好友关系，请问最终有多少个学员看到这则新闻。

本题为最基本的BFS应用，每有一个元素i入列，使ans+1，同时标记inq[i]=1。

#define MAXN 10010

int n,m;
int mmap[MAXN][MAXN], inq[MAXN];
queue<int> Q;

int main()
{
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		mmap[x][y]=true;
		mmap[y][x]=true;
	}
	Q.push(1);
	inq[1]=true;
	int ans=1;
	while(!Q.empty())
	{
		int hd=Q.front();
		for(int i=1;i<=n;i++)
		{
			if(mmap[hd][i]==true && inq[i]==false)
			{
				Q.push(i);
				ans++;
				inq[i]=true;
			}
		}
		Q.pop();
	}
	cout<<ans;
	return 0;
}

COGS152 泥潭

1
2
3

Farmer John在早晨6点准时去给贝茜挤奶，然而昨天晚上下了大雨，他的牧场变得泥泞不堪了。Farmer John的家在坐标平面的 (0,0) 处，贝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看见了所有的 N  (1 ≤ N ≤ 10,000) 个泥潭，分别在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每个泥潭只占一个点的位置。

Farmer John 刚刚买了新的靴子，他绝对不想把靴子踩进泥潭弄脏，而他又想尽快的找到贝茜。他已经快晚了，因为他花了大量的时间来找到所有的泥潭的位置。 Farmer John 只能平行于坐标轴移动，每次移动一个单位。请你帮助 Farmer John 找到一条路，使得 Farmer John 能够最快的找到贝茜，而且不会弄脏靴子。我们约定一定存在一条路使 Farmer John 找到贝茜。

本题使用结构体记录当前深度，从而得以满足题意

#define MAXN 1010

int dirx[4]={-1,1,0,0};
int diry[4]={0,0,-1,1};

struct cor
{
	int x,y,step;
};

bool mud[MAXN][MAXN], inq[MAXN][MAXN];
queue<cor>Q;
int ans;

int main()
{
	int orix,oriy,n;
	cin>>orix>>oriy>>n;
	for(int i=1,a,b;i<=n;i++)
	{
		cin>>a>>b;
		mud[a+500][b+500]=true;
	}
	Q.push({orix+500,oriy+500,0});
	ans=0;
	inq[orix+500][oriy+500]=true;
	while(!Q.empty())
	{
		cor cur=Q.front();
		if(cur.x==500&&cur.y==500) break;
		for(int i=0;i<4;i++)
		{
			int newx=cur.x+dirx[i], newy=cur.y+diry[i];
			if(newx>=0&&newx<=1000 && newy>=0&&newy<=1000 && inq[newx][newy]==false && mud[newx][newy]==false )
			{
				Q.push({newx, newy, cur.step+1});
				inq[newx][newy]=true;
			}
		}
		Q.pop();
	}
	cout<<Q.front().step;
	return 0;
}

洛谷P1949 聪明的打字员

题目待做，之后补全。