<div class="post_brief"><p>
多老的省选题了。</p>

 

就处理一下任意两个格子之间最少要经过几个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", &amp;n, &amp;m, &amp;t);
for (int i = 1; i &lt;= n; ++ i) {
	char g[maxn];
	scanf("%s", g + 1);
	for (int j = 1; j &lt;= m; ++ j)
		mp[i][j] = g[j] - 48;
}
ans = 0;
for (int i = 1; i &lt;= n; ++ i)
	for (int j = 1; j &lt;= m; ++ j)
		dijkstra(i, j);
printf("%.6lf\n", sqrt(ans));



}