[SCOI2009]最长距离

Time Limit:10000MS  Memory Limit:165536K
Total Submit:25 Accepted:16
Case Time Limit:1000MS

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

Day2
61.187.179.132:8080/JudgeOnline/showproblem
效仿tclsm神牛直接贴题目了。。感觉给我本来就很短的题解凑了点字囧。。
这道题目的感觉是SCOI2009最水的，枚举每个起点，直接BFS，复杂度是O(n^2m^2)的，同时可以规定终点的横坐标大于起点。。减少一半搜索量。。
BFS的时候注意边权可以是1也可以是0，那么用一个deque代替queue，遇到0边就放进对首，否则放进队尾就OK了。。
我从qzc神牛的代码中看到define是可以放在函数中的，而且可以用#undef给取消掉，太orz了。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<deque>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define pf push_front
using namespace std;
typedef pair<int,int> ii;
const int inf=~0U>>1,maxn=30;
int n,m,T;
double ans=0;
bool Map[maxn][maxn];
const int di[]={1,0,-1,0},dj[]={0,1,0,-1};
void bfs(int x,int y)
{
static bool vis[maxn][maxn];
static int dist[maxn][maxn];
memset(vis,0,sizeof(vis));
deque<ii> Q;dist[x][y]=Map[x][y];
vis[x][y]=true;Q.pb(ii(x,y));
#define legal(i,j) (i>=x&&i<n&&j>=0&&j<m&&!vis[i][j])
#define A first
#define B second
double tx,ty;
while(Q.size())
{
ii t=Q.front();int cost=dist[t.A][t.B],xx,yy;Q.pop_front();
if(cost>T)break;
tx=t.A-x;ty=t.B-y;
ans=max(ans,tx*tx+ty*ty);
rep(d,4)
{
xx=t.A+di[d];
yy=t.B+dj[d];
if(legal(xx,yy))
{
if(Map[xx][yy])
Q.pb(ii(xx,yy)),dist[xx][yy]=cost+1;
else
Q.pf(ii(xx,yy)),dist[xx][yy]=cost;
vis[xx][yy]=true;
}
}
}
#undef legal
#undef A
#undef B
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m>>T;char x;
rep(i,n)rep(j,m)cin>>x,Map[i][j]=x==’1′;
rep(i,n)rep(j,m)bfs(i,j);
ans=sqrt(ans);
printf("%0.6lf",ans);
}