BZOJ1295 [SCOI2009]最长距离

多老的省选题了。

就处理一下任意两个格子之间最少要经过几个1，如果小于等于t就更新答案。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define mkword(_x_,_y_) (((_x_)<<16)|(_y_))
#define hiword(_x_) ((_x_)>>16)
#define loword(_x_) ((_x_)&0x0000ffff)

const int maxn = 33;
const int maxnd = 909;
const int movx[4] = {0, 0, 1, -1};
const int movy[4] = {1, -1, 0, 0};

typedef pair <int, int> dpr;

inline int sqr(int x) {
	return x * x;
}

int n, m, t, d[maxn][maxn], ans;
int mp[maxn][maxn];
dpr hp[maxnd << 2];

void dijkstra(int i0, int j0) {
	int th(1);
	hp[0] = dpr(-mp[i0][j0], mkword(i0, j0));
	memset(d, -1, sizeof(d));
	while (th) {
		dpr g(hp[0]);
		pop_heap(hp, hp + th --);
		int x(hiword(g. second)), y(loword(g. second));
		if (d[x][y] > -1)
			continue;
		d[x][y] = - g. first;
		for (int mi = 0; mi < 4; ++ mi) {
			int i(x + movx[mi]), j(y + movy[mi]);
			if (i > 0 && i <= n && j > 0 && j <= m && d[i][j] == -1) {
				hp[th] = dpr(g. first - mp[i][j], mkword(i, j));
				push_heap(hp, hp + ++ th);
			}
		}
	}
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
			if (d[i][j] <= t) {
				int ds(sqr(i - i0) + sqr(j - j0));
				if (ds > ans)
					ans = ds;
			}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d%d", &n, &m, &t);
	for (int i = 1; i <= n; ++ i) {
		char g[maxn];
		scanf("%s", g + 1);
		for (int j = 1; j <= m; ++ j)
			mp[i][j] = g[j] - 48;
	}
	ans = 0;
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
			dijkstra(i, j);
	printf("%.6lf\n", sqrt(ans));
}