首页 > 代码库 > AOJ 0558 Cheese【BFS】
AOJ 0558 Cheese【BFS】
在H * W的地图上有N个奶酪工厂，分别生产硬度为1-N的奶酪。有一只吃货老鼠准备从老鼠洞出发吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。
老鼠从当前格走到相邻的无障碍物的格（上下左右）需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。
输入：第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)，之后H行W列为地图， “.“为空地， ”X“为障碍物，”S“为老鼠洞， 1-N代表硬度为1-N的奶酪的工厂。（中文翻译参考了http://bbs.byr.cn/#!article/ACM_ICPC/73337?au=Milrivel）
思路：吃货必须按照工厂N值从小到大的顺序吃，否则体力不济。所以这个题目其实就是求按顺序遍历地图上12345……这几个点的最短路径。说到最短路径，当然就是bfs了。
#include <iostream>#include <queue>using namespace std;int w, h, n;char map[1024][1024];// 各点到当前工厂的距离int d[1024][1024];const int direction[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 },}; int factory[16][2];typedef pair<int, int> P; //************************************// Method: bfs// FullName: bfs// Access: public // Returns: int// Parameter: const int & sx 起点x// Parameter: const int & sy 起点y// Parameter: const int & gx 终点x// Parameter: const int & gy 终点y//************************************int bfs(const int& sx, const int& sy, const int& gx, const int& gy){ //memset(d, -1, sizeof(d)); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { d[j][i] = -1; } } queue<P> que; que.push(P(sx, sy)); d[sx][sy] = 0; while (que.size()) { const P p = que.front(); que.pop(); // 如果是终点就结束 if (p.first == gx && p.second == gy) break; // 四方向漫游 for (int i = 0; i < 4; ++i) { int nx = p.first + direction[i][0]; int ny = p.second + direction[i][1]; // 是否可以移动，并且该点没有访问过 if (0 <= nx && nx < w && 0 <= ny && ny < h && map[nx][ny] != ‘X‘ && d[nx][ny] == -1) { que.push(P(nx, ny)); d[nx][ny] = d[p.first][p.second] + 1; } } } return d[gx][gy];} int main(){ cin >> h >> w >> n; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { cin >> map[j][i]; } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (map[j][i] == ‘S‘) { factory[0][0] = j; factory[0][1] = i; map[j][i] = ‘.‘; } else if (isdigit(map[j][i])) { int index = map[j][i] - ‘0‘; factory[index][0] = j; factory[index][1] = i; } } } int step = 0; for (int i = 0; i < n; ++i) { // 按顺序吃 step += bfs(factory[i][0], factory[i][1], factory[i + 1][0], factory[i + 1][1]); } cout << step << endl; return 0;}AOJ 0558 Cheese【BFS】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。