首页 > 代码库 > Hdu 2612-Find a way(bfs)
Hdu 2612-Find a way(bfs)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2612
题目大意:就是Y和M要到一个KFC商谈, 算出Y和M到KFC花费的时间和最小
题目思路:直接bfs
代码如下:
#include<bits/stdc++.h> using namespace std; struct node { int x, y, t; node(int a, int b, int c) { x = a, y = b, t = c; } }; char mp[203][203]; int arr[203][203], may[203][203]; bool mk[203][203]; int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; void bfs(int bgx, int bgy) { memset(mk, false, sizeof(mk)); queue<node> que; que.push(node(bgx, bgy, 0)); mk[bgx][bgy] = true; while( !que.empty()) { node f = que.front(); que.pop(); for(int i=0; i<4; ++ i) { int x = f.x + dir[i][0], y = f.y + dir[i][1]; int t = f.t + 1; if(mp[x][y] != ‘#‘ && mk[x][y] == false) { mk[x][y] = true; if(mp[x][y] == ‘@‘) arr[x][y] += t, may[x][y] += 1; que.push(node(x, y, t)); } } } } int main() { int n, m; while(scanf("%d%d", &n, &m) != EOF) { int y_bgx, y_bgy, m_bgx, m_bgy; memset(mp, ‘#‘, sizeof(mp)); for(int i=1; i<=n; ++ i) { for(int j=1; j<=m; ++ j) { scanf(" %c", &mp[i][j]); if(mp[i][j] == ‘Y‘) y_bgx = i, y_bgy = j; if(mp[i][j] == ‘M‘) m_bgx = i, m_bgy = j; } } memset(arr, 0, sizeof(arr)); memset(may, 0, sizeof(may)); bfs(y_bgx, y_bgy); bfs(m_bgx, m_bgy); int ans = 1000000; for(int i=1; i<=n; ++ i) { for(int j=1; j<=m; ++ j) { if(mp[i][j] == ‘@‘ && may[i][j] == 2) { if(arr[i][j] < ans) ans = arr[i][j]; } } } printf("%d\n", ans * 11); } return 0; }
Hdu 2612-Find a way(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。