hdu 2822 Dogs

朴灿烈づ我的快乐病毒、 2021-10-13 01:59 239阅读 0赞

### hdu 2822 Dogs ###

*  题意
 *  题解
 *  源代码

[传送门][Link 1]

# 题意 #

给定一个m*n的图，图中包含'X'与'.'两种字符，现在有a(x0,y0),b(x1,y1)两点
    求点a到b的最小代价(通过'X'的代价为0,'.'的代价为1)

# 题解 #

这题有点可以求两点的最短距离，不同的是，'X'与'X'之间的距离为0，其他的
    情况距离为1，所以可以用BFS求解，在求解的过程，因为不向直接最短距离一样，
    当通过'X'的代价为0，所以这个优先级一样，故可以利用优先级队列求解，按代价
    排序，代价小的级别高,当弹出b点的时候，搜索结束

# 源代码 #

#include<cstdio>
    #include<queue>
    using namespace std;
    int p[4][2]={ { -1,0},{ 1,0},{ 0,-1},{ 0,1}};//上下左右四个搜索方向
    int m,n,sx,sy,ex,ey;//(sx,sy)出发点，(es,ey)目的点
    const int maxn = 1e3+3;
    char g[maxn][maxn];
    bool visit[maxn][maxn];
    struct node
    { 
        int x,y,step;
        node(){ };
        node(int a,int b,int c):x(a),y(b),step(c){ }
        friend bool operator<(const node&A,const node&B){ 
            if(B.step==A.step){ 
                return B.x<A.x;
            }else return A.step>B.step;
        } 
    };
    
    priority_queue<node> q;
    
    int bfs(){ 
        while(!q.empty())q.pop();//清空上一次的优先级队列
        q.push(node(sx,sy,0));//出发点入队
        node a;
        for(int i=0;i<=m;++i)for(int j=0;j<=n;++j)visit[i][j]=false;//初始化
        visit[sx][sy]=true;
        while (!q.empty())
        { 
            a = q.top();
            q.pop();
            if(a.x==ex&&a.y==ey)return a.step;//目的点已搜索完
            for(int i=0;i<4;++i){ 
                int xx = a.x+p[i][0],yy=a.y+p[i][1];
                if(xx>0&&xx<=m&&yy>0&&yy<=n&&!visit[xx][yy]){ //可搜索，并为访问
                    if(g[xx][yy]=='X')q.push(node(xx,yy,a.step));
                    else q.push(node(xx,yy,a.step+1));
                    visit[xx][yy]=true;
                }
            }
        }
        
    }
    
    int main(){ 
        char c;
        while (~scanf("%d %d",&m,&n)&&(n+m))
        { 
            for(int i=1;i<=m;++i){ 
                getchar();
                for(int j=1;j<=n;++j)scanf("%c",&g[i][j]);
            }
            scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
            printf("%d\n",bfs());
        }
        
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2822