首页 > 代码库 > HDU 4771 Stealing Harry Potter's Precious(BFS + DFS)
HDU 4771 Stealing Harry Potter's Precious(BFS + DFS)
HDU 4771 Stealing Harry Potter‘s Precious
题目链接
题意:给定人的起始位置和k个宝物,求人拿完全部宝物最小的步数
思路:先bfs打出两两之间路径,然后dfs暴力求答案,因为宝物才4个,所以暴力是没问题的
代码:
#include <stdio.h> #include <string.h> #include <queue> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; const int N = 105; int n, m, k, g[10][10], vis[10]; char str[N][N]; struct Point { int x, y, num; Point(int x = 0, int y = 0) { this->x = x; this->y = y; } } s, p[10]; int bfs(Point a, Point b) { queue<Point> Q; a.num = 0; Q.push(a); int vis[N][N]; memset(vis, 0, sizeof(vis)); vis[a.x][a.y] = 1; while (!Q.empty()) { Point now = Q.front(); if (now.x == b.x && now.y == b.y) return now.num; Q.pop(); for (int i = 0; i < 4; i++) { int xx = now.x + d[i][0]; int yy = now.y + d[i][1]; if (xx <= 0 || xx > n || yy <= 0 || yy > m || str[xx][yy] == '#'|| vis[xx][yy]) continue; Point next = Point(xx, yy); next.num = now.num + 1; vis[next.x][next.y] = 1; Q.push(next); } } return -1; } bool build() { memset(g, -1, sizeof(g)); for (int i = 0; i < k; i++) { g[0][i + 1] = bfs(s, p[i]); for (int j = i + 1; j < k; j++) g[i + 1][j + 1] = g[j + 1][i + 1] = bfs(p[i], p[j]); } return true; } int dfs(int now, int num) { if (num == k) return 0; int ans = INF; for (int i = 1; i <= k; i++) { if (g[now][i] == -1 || vis[i]) continue; vis[i] = 1; ans = min(ans, dfs(i, num + 1) + g[now][i]); vis[i] = 0; } return ans; } int main() { while (~scanf("%d%d", &n, &m) && n || m) { memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) { scanf("%s", str[i] + 1); for (int j = 1; j <= m; j++) { if (str[i][j] == '@') s = Point(i, j); } } scanf("%d", &k); for (int i = 0; i < k; i++) scanf("%d%d", &p[i].x, &p[i].y); if (!build()) printf("-1\n"); else printf("%d\n", dfs(0, 0)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。