题解 | #迷宫寻宝-研发#
迷宫寻宝-研发
http://www.nowcoder.com/questionTerminal/1923918bf2b647deab161fd8d5d2ddfb
先计算每个宝箱到所有点的最短距离,然后从起点开始搜索
每次搜索前先遍历所有宝箱的位置,选定一个符合要求的宝箱后开始搜索,如果搜索完所有宝箱,返回步数,否则返回-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.... */