• 欢迎光临~

POJ 2110 Mountain Walking(二分 枚举 BFS)

开发技术 开发技术 2022-10-02 次浏览

POJ 2110 Mountain Walking(二分 枚举 BFS)

题目:

​ 给出一张(n * n(n le 100))的地图,每个点都有一个点权((val le 110)),可以任意选择路径,请问从(1, 1)走到(n, n)的路径中的最大点权和最小点权的差值的最小值是多少。

思路:

​ 捕捉最大值最小,且发现二分的复杂度是可以接受的,鉴定为二分。二分这个差值,枚举最小点权和最大点权,bfs验证是否存在这样的路径即可。

实现:

注意搜索的一些细节,防重走,限制点权范围之类的。

int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int N = 105;
int n;
int a[N][N];
int vis[N][N];

bool bfs(int lower, int upper)
{
	if(a[1][1] < lower || a[1][1] > upper)	return false;
	memset(vis, 0, sizeof vis);
	queue<PII> q;
	q.push(make_pair(1, 1));
	vis[1][1] = 1;

	while(q.size())
	{
		PII t = q.front();
		q.pop();

		if(t.first == n && t.second == n)	return true;

		rep(i, 0, 4)
		{
			int xx = t.first + d[i][0], yy = t.second + d[i][1];
			if(xx < 1 || xx > n || yy < 1 || yy > n)	continue;
			if(vis[xx][yy])	continue;
			if(a[xx][yy] < lower || a[xx][yy] > upper)	continue;

			vis[xx][yy] = 1;
			q.push(make_pair(xx, yy));
		}
	}
	return false;
}

bool check(int mid) //差值为mid
{
	for(int i = 0; i + mid <= 110; i ++)
		if(bfs(i, i + mid)) return true;
	return false;
}

int main()
{
	ios;
	cin >> n;
	rep(i, 1, n + 1)
	rep(j, 1, n + 1)
		cin >> a[i][j];

	int l = 0, r = 110;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	cout << l << 'n';
}
程序员灯塔
转载请注明原文链接:POJ 2110 Mountain Walking(二分 枚举 BFS)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com