aoj0558

今天药忘吃喽~ 2022-01-09 09:43 98阅读 0赞

一、题意： 在H \* W的地图上有N个奶酪工厂，分别生产硬度为1-N的奶酪。有一只吃货老鼠准备从老鼠洞出发吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。老鼠从当前格走到相邻的无障碍物的格（上下左右）需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。

二、思路：从0到n，做n次bfs，求出各个最短路径后相加。这里需要注意一下几点：1、没做一次bfs之前距离矩阵要初始化 2、可以在输入时就记录下起始位置和各个奶酪工厂的坐标，也可以在做bfs的过程中通过数值进行判断，都可以，只是提前记录下来写出来的代码思路会更清晰一点，所付出的就是增加一定的空间。

三、代码：

#include"iostream"
    #include"stdio.h"
    #include"queue"
    using namespace std;
    
    const int MAXN=1005;
    const int INF=100000000;
    typedef pair<int,int> P;
    
    char maze[MAXN][MAXN];
    int dist[MAXN][MAXN];
    P factory[15];
    
    int h,w,n;
    
    void DistOrigin()
    {
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                dist[i][j]=INF;
    }
    
    bool Judge(int x,int y)
    {
        if(x>=0&&x<h&&y>=0&&y<w&&maze[x][y]!='X'&&dist[x][y]==INF)
            return true;
        return false;
    }
    
    int Bfs(P pS,P pE)
    {
        queue<P> que;
        DistOrigin();
        dist[pS.first][pS.second]=0;
        que.push(pS);
    
        while(que.size())
        {
            P p=que.front();
            que.pop();
            if(p==pE) break;
            int dx[4]={0,1,0,-1};
            int dy[4]={1,0,-1,0};
            for(int i=0;i<4;i++)
            {
                int nx=p.first+dx[i];
                int ny=p.second+dy[i];
                if(Judge(nx,ny))
                {
                    dist[nx][ny]=dist[p.first][p.second]+1;
                    que.push(P(nx,ny));
                }
            }
        }
        return dist[pE.first][pE.second];
    }
    
    int main()
    {
        while(scanf("%d%d%d",&h,&w,&n)==3)
        {
            for(int i=0;i<h;i++)
            {
                for(int j=0;j<w;j++)
                {
                    cin>>maze[i][j];
                    char tmp=maze[i][j];
                    if(tmp!='.'&&tmp!='X'){
                        if(tmp=='S')
                        {
                            factory[0]=P(i,j);
                        }
                        else
                        {
                            factory[tmp-'0']=P(i,j);
                        }
                    }
                }
            }
            int sum=0;
            for(int i=0;i<n;i++)
            {
    
                int time=Bfs(factory[i],factory[i+1]);
                if(time!=INF)
                    sum+=time;
                else
                    break;
            }
            cout<<sum<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/acm-jing/p/9562915.html