# 11373: 【原1373】收集红旗比赛

### 题目描述

author: wkn/ssy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1373

## Description

“年轻人啊，都是靡靡之音呐，都是轻歌曼舞呐，将来都是没有出息的。这个啊，就是要豪迈，比如要比赛爬山啊，比赛拔河啊。”

## Input Sample

``````2 3
0 1 9
4 2 9
1 0 0
0 1 0
``````

## Output Sample

``````1
``````

## FineArtz's solution

``````/* 收集红旗比赛 */
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

const int INF = 2147483647;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

class Point{
public:
Point() = default;
Point(int xx, int yy) : x(xx), y(yy) {}

bool operator ==(Point p){
return (x == p.x && y == p.y);
}
int x = 0, y = 0, minh = INF;
};

int h[505][505];
bool v[505][505];
vector<Point> fl;
int m, n;
int ans = 0, cnt = 0;

bool check(Point p){
if (p.x < 1 || p.x > m || p.y < 1 || p.y > n || v[p.x][p.y]) return false;
return true;
}

bool bfs(Point s, int lim){
memset(v, 0, sizeof(v));
queue<Point> q;
q.push(s);
v[s.x][s.y] = true;
while (!q.empty()){
Point now = q.front();
q.pop();
for (int i = 0; i != 4; ++i){
Point next(now.x + dx[i], now.y + dy[i]);
if (check(next)){
int dh = abs(h[now.x][now.y] - h[next.x][next.y]);
if (dh > lim) continue;
q.push(next);
v[next.x][next.y] = true;
}
}
}
for (auto f : fl){
if (!v[f.x][f.y]) return false;
}
return true;
}

int main(){
memset(h, 0, sizeof(h));
cin >> m >> n;
int minn = INF, maxx = 0;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j){
cin >> h[i][j];
minn = min(minn, h[i][j]);
maxx = max(maxx, h[i][j]);
}
int flag;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j){
cin >> flag;
if (flag == 1){
fl.emplace_back(i, j);
}
}
Point s = *(fl.begin());
fl.erase(fl.begin());
s.minh = 0;
int low = 0, high = maxx - minn, mid = (low + high) / 2;
while (low < high){
mid = (low + high) / 2;
if (bfs(s, mid))
high = mid;
else
low = mid + 1;
}
cout << low << endl;
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define MAX_N 505
using namespace std;
struct data {
int height;
bool flag;
} a[MAX_N][MAX_N];
struct Node {
int x, y;
Node(int p = 0, int q = 0): x(p), y(q) {}
}s;
const int step[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
int n, m, cnt, l, r, rest;
bool vis[MAX_N][MAX_N];
queue<Node> q;
char ch = getchar(); int res = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
inline void clear(queue<Node> &q) {
queue<Node> empty;
swap(empty, q);
}
bool check(const int& delta_height) {
while (!q.empty() && rest) {
Node cur = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
Node next(cur.x + step[i][0], cur.y + step[i][1]);
if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m &&
!vis[next.x][next.y] && abs(a[next.x][next.y].height - a[cur.x][cur.y].height) <= delta_height) {
vis[next.x][next.y] = true;
if (a[next.x][next.y].flag) --rest;
q.push(next);
}
}
}
if (rest) return false;
else return true;
}
int main() {
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < m; ++j) {
r = max(r, a[i][j].height);
}
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < m; ++j) a[i][j].flag = read();
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < m; ++j)
if (a[i][j].flag) {
s.x = i, s.y = j;
++cnt;
}
l = 0;
while (l < r) {
int mid = (l + r) >> 1;
clear(q); q.push(s);
memset(vis, false, sizeof(vis)); vis[s.x][s.y] = true;
rest = cnt - 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}
``````