bzoj 1295: [SCOI2009]最长距离 暴力+bfs最短路

题目链接:

http://www.lydsy.com/JudgeOnline/problem.php?id=1295

题解:

对每个点暴力跑一遍bfs,看能够到达的最远位置,这里如果有障碍物则距离为1,如果没有障碍物,则距离为0,用bfs跑距离<=t的所有点并更新答案。

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<utility>
#include<queue>
#include<cmath>
using namespace std; double get_dis(int x,int y,int a,int b){
return sqrt(1.0*(x-a)*(x-a)+1.0*(y-b)*(y-b));
} struct Node{
int x,y,d;
Node(int x,int y,int d):x(x),y(y),d(d){}
Node(){}
bool operator < (const Node& tmp) const{
return d>tmp.d;
}
}; const int maxn=; int mp[maxn][maxn];
int n,m,t;
char str[maxn];
double ans; int d[maxn][maxn],vis[maxn][maxn];
const int dx[]={-,,,};
const int dy[]={,,-,};
void bfs(int sx,int sy,int t){
if(mp[sx][sy]==) t--;
if(t<) return;
memset(d,0x7f,sizeof(d));
memset(vis,,sizeof(vis));
priority_queue<Node> Q;
Q.push(Node(sx,sy,)),d[sx][sy]=,vis[sx][sy]=;
while(!Q.empty()){
int x=Q.top().x,y=Q.top().y;
ans=max(ans,get_dis(sx,sy,x,y));
Q.pop();
for(int i=;i<;i++){
int a=x+dx[i],b=y+dy[i];
if(a<||a>=n||b<||b>=m) continue;
if(vis[a][b]||mp[a][b]+d[x][y]>t) continue;
d[a][b]=d[x][y]+mp[a][b],vis[a][b]=,Q.push(Node(a,b,d[a][b]));
}
}
} int main(){
while(scanf("%d%d%d",&n,&m,&t)==){
for(int i=;i<n;i++){
scanf("%s",str);
for(int j=;j<m;j++){
mp[i][j]=str[j]-'';
}
}
ans=-;
for(int i=;i<n;i++){
for(int j=;j<m;j++){
bfs(i,j,t);
}
}
printf("%.6lf\n",ans);
}
return ;
}
上一篇:PHP多文件上传(二维数组$_FILES('文件域的名称'),move_uploaded_file(‘临时文件名’,‘新的文件名’))


下一篇:Java中的变量之成员变量、本地变量与类变量