题目描述
洛谷P1902刺杀大使
n, m <= 100, p(i,j) <= 1000
输入
4 2
0 0
3 5
2 4
0 0
3
输入
3
算法1
(二分+DFS)
时间复杂度
$O(nmlogp)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int p[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool st[N][N];
bool check(int x, int y, int mid)
{
bool ok = false;
st[x][y] = true;
if (x == n - 1)
{
return true;
}
for (int i = 0; i < 4; i ++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a >= 0 && a <= n - 1 && b >= 0 && b <= m - 1 && p[a][b] <= mid && !st[a][b])
{
st[a][b] = true;
ok = check(a, b, mid);
if (ok) return ok;
}
}
return ok;
}
int main()
{
cin >> n >> m;
int l = 0, r = 0;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
{
cin >> p[i][j];
if (p[i][j] > r) r = p[i][j];
}
while (l < r)
{
memset(st, 0, sizeof st);
int mid = l + r >> 1;
if (check(0, 0, mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}