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

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;
}
Leave a Reply