价格范围内最高排名的 K 样物品【经典BFS】

题目是价格范围内最高排名的 K 样物品


解题思路：

从start坐标开始遍历整张图，遍历时将当前坐标价值在合法区间的值保存下来，需要记录横、纵坐标，价格和距离四个维度因素，我们可以用一个结构体来保存遍历完后自定义优先级排序，排序优先级分别为：距离、价格、横坐标、纵坐标，从小到大排序如果结果数组长度小于k则全部输出，否则输出前k个

代码如下：

typedef struct node{ //自定义结构体，记录位置x，y和价格pricing和距离dist
    int x;
    int y;
    int pricing;
    int dist;
}no;
static bool cmp(no&a,no&b){ //自定义排序
    if(a.dist==b.dist){
        if(a.pricing==b.pricing){
            if(a.x==b.x){
                return a.y> highestRankedKItems(vector>& grid, vector& pricing, vector& start, int k) {
    int m=grid.size();
    int n=grid[0].size();
    vector>ans;
    vector>vis(m,vector(n));
    queue>q;
    vectortemp;
    q.push(make_pair(start[0],start[1]));
    vis[start[0]][start[1]]=1;
    int dist=0;
    while(!q.empty()){ //BFS
        int size=q.size();
        for(int i=0;i=pricing[0]&&grid[x][y]<=pricing[1]){
                temp.push_back({x,y,grid[x][y],dist});
            }
            for(int i=0;i<4;i++){
                int nx=x+dir[i][0];
                int ny=y+dir[i][1];
                if(nx>=0&&ny>=0&&nx0){
                    q.push(make_pair(nx,ny));
                    vis[nx][ny]=1;
                }
            }
        }
        dist++;
    }
    sort(temp.begin(),temp.end(),cmp);
    if(temp.size()					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714520.html