代价树搜索生活应用实例代码

以下是一个基于代价树搜索算法的生活应用实例代码，用于解决迷宫问题：

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

const int MAXN=1005;

int n,m,sx,sy,ex,ey;
int maze[MAXN][MAXN];
bool vis[MAXN][MAXN];

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

struct Node{
    int x,y,step;
    bool operator < (const Node &w) const {
        return step>w.step;
    }
};

int Astar(){
    priority_queue<Node> q;
    q.push((Node){sx,sy,0});

    while(!q.empty()){
        Node cur=q.top();
        q.pop();

        if(cur.x==ex && cur.y==ey) return cur.step;

        if(vis[cur.x][cur.y]) continue;
        vis[cur.x][cur.y]=true;

        for(int i=0;i<4;i++){
            int nx=cur.x+dx[i],ny=cur.y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny] || maze[nx][ny]==1) continue;
            int nstep=cur.step+1+abs(nx-ex)+abs(ny-ey);
            q.push((Node){nx,ny,nstep});
        }
    }

    return -1;
}

int main(){
    cin>>n>>m>>sx>>sy>>ex>>ey;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>maze[i][j];
        }
    }

    cout<<Astar()<<endl;

    return 0;
}

在这个例子中，我们使用优先队列实现了代价树搜索算法。通过计算每个节点到终点的估价函数，我们可以将搜索过程优化，使得搜索更加高效。在迷宫问题中，估价函数是当前节点到终点的曼哈顿距离加上当前步数，这样可以尽可能地接近最优解。