作为一个强迫症患者，小 Y 在走游戏里的迷宫时一定要把所有的宝箱收集齐才肯罢休。现在给你一个 N *M 的迷宫，里面有障碍、空地和宝箱，小 Y 在某个起始点，每一步小 Y 可以往上下左右走，当然前提时没有走出迷宫并且走到的点不是障碍。如果小 Y 走到了某个为宝箱的点，那么这个宝箱就被他收集到了，然后此处变为空地。 现在你需要计算小 Y 最少需要走多少步才能收集齐所有的宝箱。

输入包含多组数据。 对于每组数据，第一行两个正整数 N;M(1<=N;M<=100)，表示迷宫大小。 接下来 N 行，每行 M 个整数，第 i + 1 行的第 j 个整数表示迷宫第 i 行第 j 列的情况，0 表示空地，-1表示障碍，1 表示宝箱，2 表示小Y 的起始点。保证2 只有一个，且宝箱数量不超过5 个。 数据以两个0 表示结尾。

对于每组数据输出一行，包含一个整数，表示小 Y 最少的步数。如果小 Y 无法收集齐所有宝箱，输出-1。

3 5

1 -1 1 -1 2

0 -1 0 -1 0

0 0 0 0 0

0 0

#include<iostream>

#include<cstring>

#include<stdio.h>

#include<queue>

#include<algorithm>

using namespace std;

const int M=;

int n,m;

int map[M][M]; //迷宫

struct point

{

    int r;

    int l;

} p[];  //记录宝箱位置和初始位置

int run[][]= {,,-,,,,,-}; //bfs的方向数组

int bfs(point x,point y)   //求两个宝箱的最短距离

{

    int r,l,i,now,next,a[M][M]= {},mp[M][M];

    queue<int> qu;

    now=x.r*m+x.l;

    qu.push(now);

    for(i=; i<n; i++) //因为要调用计算多次，所以map不能改变，每次用map 初始mp

        for(l=; l<m; l++)

            mp[i][l]=map[i][l];

    while(!qu.empty())

    {

        now=qu.front();

        qu.pop();

        for(i=; i<; i++)

        {

            r=now/m+run[i][];

            l=now%m+run[i][];

            next=r*m+l;

            if(r>= &&r<n && l>= && l<m && mp[r][l]!=-)

            {

                a[r][l]+=a[now/m][now%m]+;

                qu.push(next);

                mp[r][l]=-;

                if(r==y.r && l==y.l)

                    return a[r][l];

            }

        }

    }

    return -; //不通时返回

}

int main()

{

    freopen("a.txt","r",stdin);

    int i,j,num,min,dis[M][M];//dis数组保存第i个宝箱到第j个宝箱的最短距离

    while(scanf("%d%d",&n,&m)!=EOF && n!= && m!=)

    {

        memset(dis,,sizeof(dis));

        int flag=;//若有宝箱不能到达的标志

        min=;

        num=;

        for(i=; i<n; i++)

            for(j=; j<m; j++)

            {

                cin>>map[i][j];

                if(map[i][j]==)

                {

                    p[].r=i;

                    p[].l=j;

                }

                if(map[i][j]==  )

                {

                    p[num].r=i;

                    p[num++].l=j;

                }

            }

        for(i=; i<num; i++)

        {

            for(j=; j<num; j++)

                if(i!=j)

                {

                    dis[i][j]=bfs(p[i],p[j]);

                    if(dis[i][j]==-)

                    {

                        flag=;

                        break;

                    }

                }

            if(flag)

                break;

        }

        if(flag)

        {

            printf("-1\n");

            continue;

        }

        char a[]= {""};

        //因为最多有5个宝箱，用这个字符串代表排列的顺序，看下面会懂的，有点妙！

        do

        {

            int s=;

            for(i=; i<num-; i++)

            {

                s+=dis[a[i]-''][a[i+]-''];

            }

            if(min>s)  //判断每种情况，

                min=s;

        }

        while(next_permutation(a+,a+num));

        //一个库函数 第一次经过他之后a[6]={"02354"}

        printf("%d\n",min);

    }

    return ;

}