这个题只用BFS来搜索一次会很麻烦, 因为每次经过一个宝藏之后,要把所有的vis重置(因为可以重复经过同一点, 但是这样会有很多不必要的路径)

看题目的暗示 最多只有5个宝藏  我们要把所有的宝藏收集齐全, 如果确定了收集的顺序, 那么也就确定了路径

那么可以知道 A55的排列一共是120种路径 遍历起来毫无压力

我们枚举所有宝藏的全排列, 然后从起点开始走, 记录整个路径的步数, 最后取最小值即可.

这里生产全排列的方法利用了 STL的next_permutation函数 非常爽....(要引入algorithm)

计算路径长度需要计算的只有 

1.起点到各个宝藏的最短距离

2.每两个宝藏之间的最短距离

所以我们用了一个dp来记忆化存储这些路径 避免重复计算

每个最短距离 用bfs来算就好了

//有一个小优化 就是 C62时一旦有任意两个box之间的距离无法达到 则直接返回-1 这样比较快

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n,m;int map[100+5][100+5];bool vis[100+5][100+5];int dx[] = {-1,1,0,0};int dy[] = {
   0,0,-1,1}; int dp[6][6]={
   0};//dp[i][j] 表示 ibox和jbox 的距离 dp[5][i] 表示起点 到i box的距离struct Point{    int x;    int y;    int id;    int step;     Point(int i=0,int j =0):x(i),y(j){        step = 0;        id = 0;     }};Point start;//二哥的起点Point boxes[5];//最多五个宝藏int path[5];//枚举的线路int len = 0; //宝藏的个数void init(){    cin>>n>>m;    for (int i = 1; i <= n; ++i){        for (int j = 1; j <= m; ++j){            cin>>map[i][j];            if(map[i][j]==1){                boxes[len].x = i;                boxes[len].y = j;                path[len] = len;                len++;            }            if(map[i][j]==2){                start.x = i;                start.y = j;                start.id = 2;                start.step = 0;             }        }    } }//int bfs(Point s, Point e){    queue
         
           q;    memset(vis,false,sizeof(vis));    s.step = 0;    q.push(s);    while(!q.empty()){        Point cur = q.front();        q.pop();        vis[cur.x][cur.y] = true;        Point next;        for (int i = 0; i < 4; ++i)        {            next.x = cur.x + dx[i];            next.y = cur.y + dy[i];            if(next.x>=1 and next.x<=n and next.y>=1 and next.y<=m)            {                if(vis[next.x][next.y])                    continue;                next.id = map[next.x][next.y];                vis[next.x][next.y] = true;                if(next.id != -1){                    next.step = cur.step + 1;                     if(next.x == e.x and next.y == e.y)//到达了终点                        return next.step;                    q.push(next);                }            }        }    }    return -1; //找不到}int build(){    //枚举取宝藏的顺序  从而形成路径 求出最小的一个即可 方案数最多 A55 = 120种    //求一下C62的dp    //生成dp    for (int i = 0; i < len; ++i)    {        dp[5][i] = bfs(start,boxes[i]);        if(dp[5][i]==-1)            return -1;    }    for (int i = 0; i < len; ++i)    {        for (int j = i+1; j < len; ++j)        {            dp[i][j] = dp[j][i] = bfs(boxes[i],boxes[j]);            if(dp[i][j]==-1)                return -1;        }    }    int ans = 1<<30;    do{        int dis = dp[5][path[0]];        for (int i = 1; i < len; ++i)        {            dis += dp[path[i]][path[i-1]];        }        ans = min(ans,dis);    }while(next_permutation(path,path+len));    return ans;}int main(int argc, char const *argv[]){     init();    cout<
          
           <