HDU2771 Stealing Harry Potter\'s Precious(bfs+dfs)

本文主要是介绍HDU2771 Stealing Harry Potter\'s Precious(bfs+dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4771

这道题的题意：求从起点经过所有的Harry's precious所在点的最小步数；

解析：BFS+DFS

BFS用来求宝贝和起点这几个点的最短路径（步数）。并用这几个点建图（双向的），然后用dfs()求经过这几个点的最小路径。。刚开始没有想到用dfs()求最短路径。（以为dijkstra）..。。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>

#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b){
    return a>b;
}
char mp[105][105];
int vis[105][105];
int vist[10];
int dir[2][4]={-1,0,1,0,0,-1,0,1};
int dist[10][10];
int ans;
struct node
{
    int x,y;
    int dist;
};
struct hh
{
    int x,y,d;
}point[50];
int n,m,k;
int sx,sy;
int bfs(int sx,int sy,int ex,int ey)
{
    cle(vis);
    int cnt=0;
    queue<node>q;
    node u;
    u.x=sx,u.y=sy,u.dist=0;
    q.push(u);
    while(!q.empty())
    {
        node u=q.front();
        q.pop();
        if(u.x==ex&&u.y==ey)return u.dist;
        for(int i=0;i<4;i++)
        {
            node v;
            v.x=u.x+dir[0][i];
            v.y=u.y+dir[1][i];
            if(mp[v.x][v.y]!='#'&&v.x<=n&&v.y<=m&&v.x>=1&&v.y>=1&&!vis[v.x][v.y])
            {
                v.dist=u.dist+1;
                q.push(v);
                vis[v.x][v.y]=1;
            }
        }
    }
    return INF;
}
void dfs(int t,int sum,int count1)
{
    if(count1==k+1)
    {
        ans=min(ans,sum);
        return;
    }
    for(int i=1;i<=k+1;i++)
    {
        if(!vist[i])
        {
            vist[i]=1;
            dfs(i,dist[t][i]+sum,count1+1);
            vist[i]=0;
        }
    }
}
int main()
{
     //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(cin>>n>>m)
    {
      if(n==0&&m==0)break;
       ///memset(dist,INF,sizeof(dist));
       cle(dist);
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='@'){point[1].x=i,point[1].y=j;}
        }
        int c,d;
        cin>>k;
        for(int i=1;i<=k;i++)
        {
            cin>>c>>d;
            point[i+1].x=c,point[i+1].y=d;
        }
        for(int i=1;i<=k+1;i++)
            for(int j=i+1;j<=k+1;j++)
           {
              dist[i][j]=dist[j][i]=bfs(point[i].x,point[i].y,point[j].x,point[j].y);
           }
           ans=INF;
           cle(vist);
           vist[1]=1;
           dfs(1,0,1);
           if(ans==INF)cout<<-1<<endl;
           else cout<<ans<<endl;
    }
    return 0;
}