学步园

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define inf 0x7fffffff

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}
const int xx[4] = {-1, 1, 0, 0}, yy[4] = {0, 0, -1, 1};
bool mp[31][31], inq[31][31];
pair<int, int> q[100001];
int n, m, t, dis[31][31];
double ans;

inline void getans(int x, int y) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (dis[i][j] <= t)
                ans = max(ans, sqrt((double) (i - x)*(double) (i - x)+(double) (j - y)*(double) (j - y)));
}

inline void spfa(int sx, int sy) {
    int t = 0, w = 1;
    memset(dis, 127, sizeof (dis));
    memset(inq, 0, sizeof (inq));
    q[t] = make_pair(sx, sy);
    dis[sx][sy] = mp[sx][sy];
    inq[sx][sy] = 1;
    while (t < w) {
        int x = q[t].first, y = q[t++].second;
        for (int i = 0; i < 4; i++) {
            int nx = x + xx[i], ny = y + yy[i];
            if (nx > n || nx < 1 || ny > m || ny < 1)continue;
            if (dis[x][y] + mp[nx][ny] < dis[nx][ny]) {
                dis[nx][ny] = dis[x][y] + mp[nx][ny];
                if (!inq[nx][ny]) {
                    q[w++] = make_pair(nx, ny);
                    inq[nx][ny] = 1;
                }
            }
        }
        inq[x][y] = 0;
    }
    getans(sx, sy);
}

int main() {
    n = read();
    m = read();
    t = read();
    for (int i = 1; i <= n; i++) {
        char ch[35];
        scanf("%s", ch);
        for (int j = 1; j <= m; j++) {
            mp[i][j] = ch[j - 1] - '0';
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            spfa(i, j);
    printf("%.6lf", ans);
    return 0;
}