【CCF-CSP】201409-4 最优配餐 C++

一、题目

原题目链接

二、解题

1.题目

一个BFS（宽度优先搜索）的实现，用于处理迷宫中的节点。下面是代码的详细解释：

1. 定义了一个node结构体，其中包括了x，y，dis三个属性。

2. 开始while循环，在队列q不为空的条件下，执行以下操作：

   a. 取出队首元素cur。

   b. 遍历cur的四个方向，计算出相邻节点的坐标并存储到tmp中。

   c. 判断节点是否越界或已被访问，如果是则跳过当前循环，继续执行下一个。

   d. 如果节点未被访问，则标记为已访问，累加上该节点值num[tmp.x][tmp.y](cur.dis+1)，并且将tmp的距离dis设为cur的距离dis+1。

   e. 将tmp加入队列q中。

3. 循环结束后，输出ans的值。

void bfs(){
	node temp;
	while(!q.empty()){
		node cur=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			temp.x=cur.x+pos[i].x;
			temp.y=cur.y+pos[i].y;
			if(temp.x<1 || temp.x>n || temp.y<1 || temp.y>n || vis[temp.x][temp.y]) continue; 
			vis[temp.x][temp.y]=true;
			ans+=num[temp.x][temp.y]*(cur.dist+1);
			temp.dist=cur.dist+1;
			q.push(temp);
		}
	}
	cout<<ans;
}

2.代码

dev c++ 5.11

#include<iostream>
#include<queue>
using namespace std;
const int N=1005;
long long num[N][N];
bool vis[N][N];
struct node{
	int x,y;
	long long dist;
};
struct POS{
	int x,y;
}pos[4]={{-1,0},{1,0},{0,-1},{0,1}};
queue<node> q;
int n;
long long ans=0;
void bfs(){
	node temp;
	while(!q.empty()){
		node cur=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			temp.x=cur.x+pos[i].x;
			temp.y=cur.y+pos[i].y;
			if(temp.x<1 || temp.x>n || temp.y<1 || temp.y>n || vis[temp.x][temp.y]) continue; 
			vis[temp.x][temp.y]=true;
			ans+=num[temp.x][temp.y]*(cur.dist+1);
			temp.dist=cur.dist+1;
			q.push(temp);
		}
	}
	cout<<ans;
}

int main(){
	int m,k,d,x,y,c;
	cin>>n>>m>>k>>d;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		q.push({x,y,0});
	}
	for(int i=0;i<k;i++){
		cin>>x>>y>>c;
		num[x][y]+=c;
	}
	for(int i=0;i<d;i++){
		cin>>x>>y;
		vis[x][y]=true;
	}
	bfs();
	return 0; 
} 

3.提交结果

总结

1.代码思路

这道题可以使用 BFS（广度优先搜索）解决。思路如下：

1. 将选定的餐厅进入队列。

2. 遍历队列，每次取出队首的元素，进行以下操作：

（1）将四周没有障碍物（大街）且没有被访问过的点入队。

（2）将距离前面一个点的距离加一，作为这个点的距离，并将这个点的贡献值累加到答案中。

3. 遍历结束后，打印出答案。

实现时，需要用 bool 数组 vis[] [] 来记录每个点是否被访问过，用 long long 数组 num[] [] 记录每个点对答案的贡献值。

代码中 queue 存放的节点包含三个属性：x 和 y 表示它在矩阵中的位置，dist 表示这个点到达时的距离。