题解 | #迷宫寻宝-研发#

先计算每个宝箱到所有点的最短距离，然后从起点开始搜索
每次搜索前先遍历所有宝箱的位置，选定一个符合要求的宝箱后开始搜索，如果搜索完所有宝箱，返回步数，否则返回-1

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int x,y,t;
}A[10];

char mp[55][55];
bool book[55][55];
int dp[55][55][10];//记录宝箱到每个点的最短距离 
int m,n;
int tx[4] = {0,1,0,-1};
int ty[4] = {1,0,-1,0};
int cnt;
void bfs(int x, int y, int id)//计算宝箱到每个点的最短距离 
{
    memset(book,0,sizeof(book));
    int cnt = 0;
    queue<node> q;
    node a;
    a.x = x;
    a.y = y;
    a.t = 0;
    book[x][y] = true;
    q.push(a);
    while(!q.empty())
    {
        node w = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int xx = w.x + tx[i];
            int yy = w.y + ty[i];
            int temp = w.t+1;
            if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && !book[xx][yy] && mp[xx][yy] != '#')
            {
                book[xx][yy] = true;
                dp[xx][yy][id] = temp;
                q.push(node{xx,yy,temp});
            }
        }
    }
}

int Bfs(int x, int y, int t) 
{
    node a;
    a.x = x;
    a.y = y;
    a.t = t;
    memset(book,0,sizeof(book));
    book[x][y] = 1;
    queue<node> q;
    q.push(a);
    int p = 0;
    while(!q.empty())
    {
        node w = q.front();
        q.pop();
        if(mp[w.x][w.y] >= '0' && mp[w.x][w.y] <= '9' && A[mp[w.x][w.y] - '0'].t == 0)
        {
            memset(book,0,sizeof(book));
            book[w.x][w.y] = 1;
            A[mp[w.x][w.y] - '0'].t = 1;
            p++;
        }
        if(p == cnt)
        {
            return w.t;
        }
        int maxn = 100005;
        int id;
        for(int i = 0; i < cnt; i++)
        {
            if(abs(A[i].x - w.x) + abs(A[i].y - w.y) < maxn && A[i].t == 0)
            {
                maxn = abs(A[i].x - w.x) + abs(A[i].y - w.y);
                id = i;
            }
        }
        for(int i = 0; i < 4; i++)
        {
            int xx = w.x + tx[i];
            int yy = w.y + ty[i];
            int temp = w.t+1;
            if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && !book[xx][yy] && mp[xx][yy] != '#' && dp[xx][yy][id] < dp[w.x][w.y][id])
            {
                book[xx][yy] = 1;
                q.push(node{xx,yy,temp});
            }
        }
    }
    return -1;
}
int main()
{
    int t,x,y;
    cin >> t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        cnt = 0;
        cin >> m >> n;
        cnt = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                cin >> mp[i][j];
                if(mp[i][j] == '*')
                {
                    x = i;
                    y = j;
                }
                else if(mp[i][j] >= '0' && mp[i][j] <= '9')
                {
                    A[mp[i][j] - '0'].x = i;
                    A[mp[i][j] - '0'].y = j;
                    cnt++;
                }
            }
        }
        for(int i = 0; i < cnt; i++)
        {
            bfs(A[i].x, A[i].y, i);
        }
        int ans = Bfs(x,y,0);
        cout << ans << "\n";
        for(int i = 0; i < cnt; i++)
        {
            A[i].t = 0;
            A[i].x = 0;
            A[i].y = 0;
        }
    }
} 

/*
链接：https://www.nowcoder.com/questionTerminal/1923918bf2b647deab161fd8d5d2ddfb
来源：牛客网

3
5 5
0...1
.#.#.
..*..
.#.#.
2...3
5 5
0...1
.#.#.
..*.#
.#.#.
2.#.3
5 5
....1
.####
..*..
####.
0....
*/