放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 广度优先搜索

AOJ 0558 Cheese

在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
// Qualifier:
// 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];
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	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;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》