洛谷P1902 刺杀大使

二分加广搜
#include <bits/stdc++.h>

using namespace std;

int n, m, l, r, p[1001][1001], vis[1001][1001];

int dx[6] = {0, 1, -1, 0, 0};

int dy[6] = {0, 0, 0, 1, -1};

int qx[100100], qy[1001001];

bool check(int d)

{

	memset(vis, 0, sizeof(vis));

	int front = 0, tail = 0;

	for (int i = 1; i <= m; i++)

		qx[++tail] = i, qy[tail] = 1;

	int tot = 0;

	while (front <= tail)

	{

		int nx = qx[front], ny = qy[front++];

		if (ny == n)

			tot++;

		for (int i = 1; i <= 4; i++)

		{

			int ax = nx + dx[i];

			int ay = ny + dy[i];

			if (p[ay][ax] <= d && !vis[ay][ax] && (ax <= m && ax >= 1 && ay <= n && ay >= 1))

				qx[++tail] = ax, qy[tail] = ay, vis[ay][ax] = 1;

		}

	}

	if (tot == m) return 1;

	return 0;

}

int main()

{

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++)

		for (int j = 1; j <= m; j++)

			scanf("%d", &p[i][j]), r = max(r, p[i][j]);

	int mid = 0, ans = 0;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (check(mid))

			ans = mid, r = mid - 1;

		else l = mid + 1;

	}

	printf("%d", ans);

	return 0;

}
巴特西

洛谷P1902 刺杀大使

最新文章

热门文章
