首页 > 代码库 > hdu-2612 两次bfs
hdu-2612 两次bfs
http://acm.hdu.edu.cn/showproblem.php?pid=2612
两次bfs, 记录到每个KFC的最短时间。选取最短时间。
#include <stdio.h> #include <iostream> #include <string> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <set> #include <map> #include <vector> using namespace std; int n, m; int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }; int check(int x, int y) { if (x >= 1 && x <= n && y >= 1 && y <= m) return 1; return 0; } struct node { int x; int y; int t1, t2; char c; }p[210][210]; int vis[210][210]; int sx, sy; int ex, ey; void bfs(int x,int y) { memset(vis,0,sizeof(vis)); queue<node> q; node qq, qqq; qq.x = x; qq.y = y; qq.t1 = 0; p[x][y].t1 = 0; vis[x][y] = 1; q.push(qq); while (!q.empty()) { qq = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = qq.x + dir[i][0]; int y = qq.y + dir[i][1]; if (!check(x, y) || vis[x][y] || p[x][y].c == '#') continue; vis[x][y] = 1; qqq.x = x; qqq.y = y; qqq.t1 = qq.t1 + 1; p[x][y].t1 = qqq.t1; q.push(qqq); } } return; } void bfs1(int x, int y) { memset(vis, 0, sizeof(vis)); queue<node> q; node qq, qqq; qq.x = x; qq.y = y; qq.t2 = 0; p[x][y].t2 = 0; vis[x][y] = 1; q.push(qq); while (!q.empty()) { qq = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = qq.x + dir[i][0]; int y = qq.y + dir[i][1]; if (!check(x, y) || vis[x][y] || p[x][y].c == '#') continue; vis[x][y] = 1; qqq.x = x; qqq.y = y; qqq.t2 = qq.t2 + 1; p[x][y].t2 = qqq.t2; q.push(qqq); } } return; } int main() { while (cin >> n >> m) { getchar(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> p[i][j].c; if (p[i][j].c == 'Y') { sx = i; sy = j; } if (p[i][j].c == 'M') { ex = i; ey = j; } } getchar(); } bfs(sx,sy); bfs1(ex,ey); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (p[i][j].c == '@') { p[i][j].t1 = (p[i][j].t1+p[i][j].t2); } } int ans = 10000000; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (p[i][j].c == '@') { ans = min(p[i][j].t1, ans); } } ans *= 11; cout << ans << endl; } return 0; }
hdu-2612 两次bfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。