hdu 4771 Stealing Harry Potter's Precious

全栈程序员-用户IM • 2021年12月16日下午6:00 • 未分类

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

hdu 4771 Stealing Harry Potter's Precious

此处内容已经被作者隐藏，请输入验证码查看内容

请关注本站微信公众号，回复“”，获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

题目：给出一个二维图，以及一个起点，m个中间点，求出从起点出发，到达每一个中间的最小步数。

思路：由于图的大小最大是100*100，所以要使用bfs求出当中每两个点之间的最小距离。然后依据这些步数，建立一个新的图，使用dfs求出最佳步数。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 100000000
using namespace std;
char ma[103][103];
int vis[103][103];
int map[6][6],net[6];
int m,n,k;
struct node
{
    int x,y;
    int k;
}t;
queue<node>q;
int bfs(int x,int y,int l,int r)
{
    memset(vis,0,sizeof(vis));
    while(!q.empty())
    {
        q.pop();
    }
    vis[x][y]=1;
    t.x=x,t.y=y,t.k=0;
    q.push(t);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        x=t.x;y=t.y;
        if(x==l&&y==r)
        {
            return t.k;
        }
        t.k++;
        if(x>=2&&ma[x-1][y]!='#'&&!vis[x-1][y])
        {
            t.x=x-1;t.y=y;
            vis[t.x][t.y]=1;
            q.push(t);
        }
        if(y>=2&&ma[x][y-1]!='#'&&!vis[x][y-1])
        {
            t.x=x;t.y=y-1;
            vis[t.x][t.y]=1;
            q.push(t);
        }
        if(x+1<=m&&ma[x+1][y]!='#'&&!vis[x+1][y])
        {
            t.x=x+1;t.y=y;
            vis[t.x][t.y]=1;
            q.push(t);
        }
        if(y+1<=n&&ma[x][y+1]!='#'&&!vis[x][y+1])
        {
            t.x=x;t.y=y+1;
            vis[t.x][t.y]=1;
            q.push(t);
        }
    }
    return INF;
}
int ans=INF;
void dfs(int x,int step,int sum)
{
    if(step==k)
    {
        if(ans>sum) ans=sum;
        return;
    }
    for(int i=0;i<=k;i++)
    if(!net[i])
    {
       net[i]=1;
       dfs(i,step+1,sum+map[x][i]);
       net[i]=0;
    }
}
int main()
{
    int d[6][2];
    while(cin>>m>>n,m,n)
    {
        int x=0,y=0,l,r,sum;
        ans=INF;
        for(int i=1;i<=m;i++)
        {
            scanf("%s",&ma[i][1]);
            if(!x)
                for(int j=1;j<=n;j++)
                if(ma[i][j]=='@')
                {
                  x=i,y=j;
                  break;
                }
        }
        d[0][0]=x;d[0][1]=y;
        cin>>k;
        for(int i=1;i<=k;i++)
        {
            cin>>d[i][0]>>d[i][1];
        }
        for(int i=0;i<k;i++)
        {
            x=d[i][0],y=d[i][1];
            for(int j=i+1;j<=k;j++)
            {
                l=d[j][0],r=d[j][1];
                sum=bfs(x,y,l,r);
                if(sum<INF) map[i][j]=map[j][i]=sum;
                else map[i][j]=map[j][i]=INF;
                //cout<<sum<<endl;
            }
        }
        net[0]=1;
        dfs(0,0,0);
        if(ans<INF) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/117918.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...