bfs最短路。

写的真丑。。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn = 50;
const int INF = 0x3f3f3f3f;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1}; int n,m,T;
int a[maxn][maxn],id[maxn][maxn],vid;
char s[maxn];
int xx,x2,yy,y2,h,d[1000][maxn][maxn];
int ans;
double res; struct Point {
int x,y;
} q[1000]; void bfs(int x,int y) {
h=id[x][y]=++vid;
int l=0,r=1;
q[0].x=x; q[0].y=y;
if(a[x][y]) d[h][x][y]=1;
else d[h][x][y]=0;
while(l<r) {
xx=q[l].x,yy=q[l].y; l++;
for(int i=0;i<4;i++) {
x2=xx+dx[i];
y2=yy+dy[i];
if(x2<1 || x2>n || y2<1 || y2>m) continue;
if(a[x2][y2]) {
if(d[h][x2][y2] > d[h][xx][yy]+1) {
d[h][x2][y2]=d[h][xx][yy]+1;
if(d[h][x2][y2]<=T) {
q[r].x=x2;
q[r].y=y2;
r++;
}
}
}
else if(d[h][x2][y2]>d[h][xx][yy]) {
d[h][x2][y2]=d[h][xx][yy];
if(d[h][x2][y2]<=T) {
q[r].x=x2;
q[r].y=y2;
r++;
}
}
}
}
} inline int sqr(int x) {
return x*x;
} int cal(int x1,int y1,int x2,int y2) {
return sqr(x1-x2)+sqr(y1-y2);
} int main() {
memset(d,0x3f,sizeof(d));
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
for(int j=1;j<=m;j++) if(s[j]=='1') a[i][j]=1;
else a[i][j]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
bfs(i,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
h=id[i][j];
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
if(d[h][x][y]<=T) ans=max(ans,cal(i,j,x,y));
}
res=sqrt(ans);
printf("%0.6f\n",res);
return 0;
}

最新文章

  1. ASP.NET 5 Beta 7 版本
  2. Dedesql数据库类详解
  3. Repeater导航菜单DataList产品展示
  4. git使用小结
  5. (转)MySQL Workbench的使用教程 (初级入门版)
  6. Android 圆角Button
  7. Struts2项目中使用Ajax报错
  8. Android学习——百度地图开发定位与显示Demo
  9. 在网络通讯中应用Protobuf
  10. LeetCode OJ 121. Best Time to Buy and Sell Stock
  11. El表达式取map值
  12. System.ComponentModel.DataAnnotations 冲突
  13. unity图片后期处理
  14. bzoj 1188 [HNOI2007]分裂游戏 SG函数 SG定理
  15. 关于ehcache缓存中eternal及timeToLiveSeconds和timeToIdleSeconds的说明
  16. jmeter连接oracle数据库配置
  17. linux系统中使用socket直接发送ARP数据
  18. boostrap常用的类
  19. 洛谷 3295 [SCOI2016]萌萌哒——并查集优化连边
  20. 一个worker thread服务一个客户端

热门文章

  1. dbt
  2. 手写一个自己的简单MVC框架myPHP
  3. delphi调用 java 的 WebService服务端.
  4. Failed to execute command: &quot;&quot;C:\Program Files (x86)\Microsoft SDKs\Windows\v7.0A\Bin\ResGen.exe&quot; 的一个解决办法
  5. IOS平台汉字转拼音方案
  6. EXTJS 4.2 资料 控件之 Store 用法
  7. having与where区别
  8. 预告:准备开个坑,集中学习一下esp32模块
  9. 1059: [ZJOI2007]矩阵游戏 - BZOJ
  10. SNMP的工作原理&amp;软件开发