### 第11届浙江大学校赛比赛点评beta » ZOJ3477bf

ZOJ3477bf.cpp

```#include <deque>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int MAXN = 2048;
const int INF = 2000000000;

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

int d[MAXN][MAXN];

int main() {
int r, c, n, x, y, z, xx, yy;
vector<pair<int, pair<int, int> > > v;

while (scanf("%d%d%d", &r, &c, &n) != EOF) {
v.clear();
for (int i = 0; i < n; ++i) {
scanf("%d%d%d", &x, &y, &z);
v.push_back(make_pair(z, make_pair(x, y)));
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
d[i][j] = -1;
}
}

deque<pair<int, int> > q;
while (!q.empty() || !v.empty()) {
z = q.empty() ? INF : d[q.front().first][q.front().second];
while (!v.empty() && v.back().first <= z) {
x = v.back().second.first;
y = v.back().second.second;
z = v.back().first;
if (d[x][y] == -1) {
d[x][y] = z;
q.push_front(v.back().second);
}
v.pop_back();
}

if (!q.empty()) {
x = q.front().first;
y = q.front().second;
z = d[x][y];
q.pop_front();
for (int i = 0; i < 4; ++i) {
xx = x + dx[i];
yy = y + dy[i];
if (1 <= xx && xx <= r && 1 <= yy && yy <= c && d[xx][yy] == -1) {
d[xx][yy] = z + 1;
q.push_back(make_pair(xx, yy));
}
}
}
}

z = -1;
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
if (d[i][j] > z) {
z = d[i][j];
x = i;
y = j;
}
}
}
//	fprintf(stderr, "%d (%d*%d*%d*%d)\n", (x - 1) * (r - x) * (y - 1) * (c - y), x - 1, y - 1, r - x, c - y);
printf("%d (%d, %d)\n", z, x, y);
}

return 0;
}
```