POJ 2110 Mountain Walking（二分 枚举 BFS）

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';
}