題目鏈接：hdu 4771 Stealing Harry Potter's Precious

題目大意：在一個(gè)N*M的銀行里，賊的位置在’@‘，如今給出n個(gè)寶物的位置。如今賊要將全部的寶物拿到手。問最短的路徑，不須要考慮離開。

解題思路：由于寶物最多才4個(gè)，加上賊的位置，枚舉兩兩位置，用bfs求兩點(diǎn)距離，假設(shè)存在兩點(diǎn)間不能到達(dá)，那么肯定是不能取全然部的寶物。

然后枚舉取寶物的順序。維護(hù)ans最小。

#include <cstdio> #include <cstring> #include <queue> #include <algorithm>using namespace std; const int maxn = 100; const int maxv = 10; const int INF = 0x3f3f3f3f; const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };struct point {int x, y;point (int x = 0, int y = 0) {this->x = x;this->y = y;} } p[maxv];char g[maxn+5][maxn+5]; int n, N, M, v[maxn+5][maxn+5], d[maxv][maxv];void init () {memset(g, 0, sizeof(g));for (int i = 1; i <= N; i++) {scanf("%s", g[i] + 1);for (int j = 1; j <= M; j++)if (g[i][j] == '@') {p[0].x = i;p[0].y = j;}}scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d%d", &p[i].x, &p[i].y); }int bfs (point s, point e) {queue<point> que;memset(v, -1, sizeof(v));que.push(s);v[s.x][s.y] = 0;while (!que.empty()) {point u = que.front();que.pop();if (u.x == e.x && u.y == e.y)return v[u.x][u.y];for (int i = 0; i < 4; i++) {int xi = u.x + dir[i][0];int yi = u.y + dir[i][1];if (xi > N || xi <= 0)continue;if (yi > M || yi <= 0)continue;if (v[xi][yi] != -1 || g[xi][yi] == '#')continue;que.push(point(xi, yi));v[xi][yi] = v[u.x][u.y] + 1;}}return -1; }bool judge () {memset(d, 0, sizeof(d));for (int i = 0; i <= n; i++) {for (int j = i + 1; j <= n; j++) {int dis = bfs(p[i], p[j]);if (dis == -1)return false;d[i][j] = d[j][i] = dis;}}return true; }int solve () {int pos[maxv];for (int i = 0; i <= n; i++)pos[i] = i;int ans = INF;do {int sum = 0;for (int i = 0; i < n; i++)sum += d[pos[i]][pos[i+1]];ans = min (ans, sum);} while(next_permutation(pos + 1, pos + n + 1));return ans; }int main () {while (scanf("%d%d", &N, &M) == 2 && N + M) {init();if (judge()) {printf("%d\n", solve());} elseprintf("-1\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 4771 Stealing Harry Potter#39;s Precious(bfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。