BZOJ1295: [SCOI2009]最长距离

1295: [SCOI2009]最长距离

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1719 Solved: 935
[Submit][Status][Discuss]

Description

windy 有一块矩形土地，被分为 N*M 块 1*1 的小格子。有的格子含有障碍物。如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A不可以走到格子B，就没有距离。如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。如果windy可以移走T块障碍物，求所有格子间的最大距离。保证移走T块障碍物以后，至少有一个格子不含有障碍物。

Input

输入文件maxlength.in第一行包含三个整数，N M T。接下来有N行，每行一个长度为M的字符串，'0'表示空格子，'1'表示该格子含有障碍物。

Output

输出文件maxlength.out包含一个浮点数，保留6位小数。

Sample Input

【输入样例一】
3 3 0
001
001
110

【输入样例二】
4 3 0
001
001
011
000

【输入样例三】
3 3 1
001
001
001

Sample Output

【输出样例一】
1.414214

【输出样例二】
3.605551

【输出样例三】
2.828427

HINT

20%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 0 。 40%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 2 。 100%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 30 。

Source

曾经觉得很神的做法，现在已经沦为水题。

可曾经，我还有考NOIP2017的机会

现在没了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <queue>
 8 #include <vector>
 9 #define min(a, b) ((a) < (b) ? (a) : (b))
10 #define max(a, b) ((a) > (b) ? (a) : (b))
11 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
12 inline void swap(int &a, int &b)
13 {
14     int tmp = a;a = b;b = tmp;
15 }
16 inline void read(int &x)
17 {
18     x = 0;char ch = getchar(), c = ch;
19     while(ch < '0' || ch > '9') c = ch, ch = getchar();
20     while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
21     if(c == '-')x = -x;
22 }
23 
24 const int INF = 0x3f3f3f3f;
25 const int MAXN = 30 + 10;
26 const int dx[4] = {0,0,1,-1};
27 const int dy[4] = {1,-1,0,0};
28 
29 int n,m,t,ans[MAXN][MAXN][MAXN][MAXN];
30 bool g[MAXN][MAXN]; 
31 
32 struct Node
33 {
34     int x,y;
35     Node(int _x, int _y){x = _x;y = _y;}
36     Node(){}
37 }q[MAXN * MAXN * MAXN * MAXN];
38 
39 int d[MAXN][MAXN], b[MAXN][MAXN], he, ta;
40 
41 void spfa(int sx, int sy)
42 {
43     memset(d, 0x3f, sizeof(d));
44     memset(b, 0, sizeof(b));
45     he = 0, ta = 1;
46     d[sx][sy] = g[sx][sy];
47     b[sx][sy] = 1;
48     q[he] = Node(sx, sy);
49     while(he < ta)
50     {
51         Node now = q[he ++];
52         b[now.x][now.y] = 0;
53         for(register int i = 0;i < 4;++ i)
54         {
55             int xx = now.x + dx[i], yy = now.y + dy[i];
56             if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
57             if(d[now.x][now.y] + g[xx][yy] < d[xx][yy])
58             {
59                 d[xx][yy] = d[now.x][now.y] + g[xx][yy];
60                 if(!b[xx][yy]) q[ta ++] = Node(xx, yy), b[xx][yy] = 1;
61             }
62         } 
63     } 
64 }
65 
66 char s[MAXN];
67 
68 int main()
69 {
70     read(n), read(m), read(t);
71     for(register int i = 1;i <= n;++ i)
72     {
73         scanf("%s", s + 1);
74         for(register int j = 1;j <= m;++ j)
75             g[i][j] = s[j] - '0';
76     }
77     for(register int i = 1;i <= n;++ i) for(register int j = 1;j <= m;++ j) 
78     {
79         spfa(i,j);
80         for(register int a = 1;a <= n;++ a) for(register int b = 1;b <= m;++ b) ans[i][j][a][b] = d[a][b];
81     }
82     double p = 0;
83     for(register int i = 1;i <= n;++ i)
84         for(register int j = 1;j <= m;++ j)
85             for(register int a = 1;a <= n;++ a)
86                 for(register int b = 1;b <= m;++ b)
87                     if(ans[i][j][a][b] <= t)
88                         p = max(p, sqrt(abs(i - a) * abs(i - a) + abs(j - b) * abs(j - b)));
89     printf("%.6lf", p);
90     return 0;
91 }

BZOJ1295