1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
| #include <cstdio> #include <climits> #include <cmath> #include <queue> #include <algorithm> const int MAXN = 35; struct Node { int dist, x, y; bool vis; } N[MAXN][MAXN]; int n, m, t; int G[MAXN][MAXN]; namespace Dijkstra { struct HeapNode { Node *u; int dist; bool operator<(const HeapNode &another) const { return dist > another.dist; } }; bool valid(int x, int y) { return x <= n && x > 0 && y <= m && y > 0; } const int d[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; void dijkstra(Node *s) { std::priority_queue<HeapNode> q; s->dist = G[s->x][s->y]; q.push((HeapNode) {s, 0}); while (!q.empty()) { Node *u = q.top().u; q.pop(); if (u->vis) continue; u->vis = true; for (int i = 0; i < 4; i++) { int x = u->x + d[i][0], y = u->y + d[i][1]; if (!valid(x, y)) continue; Node *v = &N[x][y]; if (v->dist > u->dist + G[x][y] && u->dist + G[x][y] <= t) { v->dist = u->dist + G[x][y]; q.push((HeapNode) {v, v->dist}); } } } } void solve(int x, int y) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { N[i][j].vis = false; N[i][j].dist = INT_MAX; } dijkstra(&N[x][y]); } } int dist(int x1, int y1, int x2, int y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } int main() { scanf("%d %d %d", &n, &m, &t); for (int i = 1; i <= n; i++) { static char s[MAXN]; scanf("%s", s + 1); for (int j = 1; j <= m; j++) { G[i][j] = s[j] - '0'; N[i][j].x = i; N[i][j].y = j; } } int ans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { Dijkstra::solve(i, j); for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) if (N[x][y].dist <= t) ans = std::max(ans, dist(i, j, x, y)); } printf("%.6lf\n", sqrt(ans)); return 0; }
|