首页 > 代码库 > (SPFA) bzoj 1295

(SPFA) bzoj 1295

2024-11-24 15:27:39   202人阅读

1295: [SCOI2009]最长距离

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 922  Solved: 478
[Submit][Status]

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
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<cstdlib>#include<algorithm>#include<queue>using namespace std;#define INF 0x7fffffffqueue<int> q;int n,m,t,a[50][50],vis[50][50],d[50][50];int dic[4][2]={{1,0},{-1,0},{0,1},{0,-1}};char s[50][50];double dis(int i,int j,int ii,int jj){      return sqrt((double)((ii-i)*(ii-i)+(jj-j)*(jj-j)));}bool check(int x,int y){      if(x<0||y<0||x>=n||y>=m)            return false;      return true;}void SPFA(int sx,int sy){     int xx,yy;     while(!q.empty()) q.pop();     memset(vis,0,sizeof(vis));     for(int i=0;i<n;i++)     {           for(int j=0;j<m;j++)                  d[i][j]=INF;     }     vis[sx][sy]=1;     d[sx][sy]=a[sx][sy];     q.push(sx),q.push(sy);     while(!q.empty())     {           int x,y;           x=q.front(),q.pop();           y=q.front(),q.pop();           for(int i=0;i<4;i++)           {                 xx=x+dic[i][0],yy=y+dic[i][1];                 if(!check(xx,yy)) continue;                 if(d[x][y]+a[xx][yy]<d[xx][yy]&&d[x][y]+a[xx][yy]<=t)                 {                       d[xx][yy]=d[x][y]+a[xx][yy];                       if(!vis[xx][yy])                       {                             vis[xx][yy]=1;                             q.push(xx),q.push(yy);                       }                 }           }           vis[x][y]=0;     }}int main(){      double ans;      memset(a,0,sizeof(a));      scanf("%d%d%d",&n,&m,&t);      for(int i=0;i<n;i++)            scanf("%s",s[i]);      for(int i=0;i<n;i++)      {            for(int j=0;j<m;j++)            {                  if(s[i][j]==‘0‘)                        a[i][j]=0;                  else if(s[i][j]==‘1‘)                        a[i][j]=1;            }      }      for(int i=0;i<n;i++)      {            for(int j=0;j<m;j++)            {                  SPFA(i,j);                  for(int ii=0;ii<n;ii++)                  {                        for(int jj=0;jj<m;jj++)                        {                              if(d[ii][jj]<=t)                                    ans=max(ans,dis(i,j,ii,jj));                        }                  }            }      }      printf("%.6lf\n",ans);      return 0;}

　　

(SPFA) bzoj 1295


联系
我们