bzoj1295: [SCOI2009]最长距离
2024-09-21 20:29:25
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;
}
最新文章
- ASP.NET 5 Beta 7 版本
- Dedesql数据库类详解
- Repeater导航菜单DataList产品展示
- git使用小结
- (转)MySQL Workbench的使用教程 (初级入门版)
- Android 圆角Button
- Struts2项目中使用Ajax报错
- Android学习——百度地图开发定位与显示Demo
- 在网络通讯中应用Protobuf
- LeetCode OJ 121. Best Time to Buy and Sell Stock
- El表达式取map值
- System.ComponentModel.DataAnnotations 冲突
- unity图片后期处理
- bzoj 1188 [HNOI2007]分裂游戏 SG函数 SG定理
- 关于ehcache缓存中eternal及timeToLiveSeconds和timeToIdleSeconds的说明
- jmeter连接oracle数据库配置
- linux系统中使用socket直接发送ARP数据
- boostrap常用的类
- 洛谷 3295 [SCOI2016]萌萌哒——并查集优化连边
- 一个worker thread服务一个客户端
热门文章
- dbt
- 手写一个自己的简单MVC框架myPHP
- delphi调用 java 的 WebService服务端.
- Failed to execute command: ";";C:\Program Files (x86)\Microsoft SDKs\Windows\v7.0A\Bin\ResGen.exe"; 的一个解决办法
- IOS平台汉字转拼音方案
- EXTJS 4.2 资料 控件之 Store 用法
- having与where区别
- 预告:准备开个坑,集中学习一下esp32模块
- 1059: [ZJOI2007]矩阵游戏 - BZOJ
- SNMP的工作原理&;软件开发