hdu 1242 Rescue(BFS+优先队列)

hdu 1242 Rescue(BFS+优先队列)

起初只是用DFS做，但后来发现问题太多了，起点是一个，但可能有多个士兵，要找到最小的距离即要求每一个子问题的结果都是最小值。用深度优先搜索自然不能每次都返回较小值。而广度优先搜索就像使用了分身术一样，4个方向都有friend去找angel，各自返回自己的最小值，所以思路就是BFS+优先队列。

#include#include#include#includeusing namespace std;char imap[211][211];int n,m,x_s,y_s,x_e,y_e; struct node{    int x,y,step;    friend bool operator<(node n1,node n2) // 不能是 bool operator<(node n1,node n2)哦    {        return n2.step=0&&x=0&&yq;    node cur,next;    int i;    cur.x=x_s;    cur.y=y_s;    cur.step=0;    imap[cur.x][cur.y]='#';    q.push(cur);    while(!q.empty())    {        cur=q-();        q.pop();        if(cur.x==x_e && cur.y==y_e)    return cur.step; //返回最小值        for(i=0;i<4;i++)        {            next.x=cur.x+dir[i][0];            next.y=cur.y+dir[i][1];            if(!judge(next.x,next.y)) continue;            if(imap[next.x][next.y]=='x') next.step=cur.step+2;            else   next.step=cur.step+1;            imap[next.x][next.y]='#';            q.push(next);        }        //cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。