BFS进阶刷题

P2658 汽车拉力比赛

#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;
#define int long long
int n, m;
int high[505][505];
int flag[505][505];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int count;
int dis[505][505];
int startx, starty;
bool bfs(int mid)
{int sum = 1;memset(dis, -1, sizeof dis);queue<pair<int, int>> q;q.push({startx, starty});dis[startx][starty] = 0;if (sum == count){return true;}while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx < 1 || ny < 1 || nx > n || ny > m){continue;}if (dis[nx][ny] != -1){continue;}int nd = abs(high[nx][ny] - high[t.first][t.second]);if (nd <= mid){dis[nx][ny] = dis[t.first][t.second] + 1;q.push({nx, ny});if (flag[nx][ny] == 1){sum++;if (sum == count){return true;}}}}}return false;
}
signed main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> high[i][j];}}count = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> flag[i][j];if (flag[i][j] == 1){count++;if (startx == 0){startx = i;starty = j;}}}}int left = -1;int right = INT_MAX;while (left + 1 < right){int mid = (left + right) / 2;if (bfs(mid)){right = mid;}else{left = mid;}}cout << right;return 0;
}