题面
https://www.luogu.org/problem/P4162
题解
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define ri register int #define N 33 using namespace std; const int dx[]={1,-1,0,0},dy[]={0,0,-1,1}; char g[N][N]; int n,m,d; int dis[N][N]; double dist(int x1,int y1,int x2,int y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } struct node{ int x,y; int s; }; deque<node> q; int main(){ scanf("%d %d %d",&n,&m,&d); memset(g,'#',sizeof(g)); for (ri i=1;i<=n;i++) { scanf("%s",g[i]+1); g[i][m+1]='#'; } double ans=0; for (ri ii=1;ii<=n;ii++) for (ri jj=1;jj<=m;jj++) { memset(dis,0x3f,sizeof(dis)); int cc; if (g[ii][jj]=='1') cc=1; else cc=0;dis[ii][jj]=cc; q.push_back((node){ii,jj,cc}); while (!q.empty()) { node cur=q.front(); q.pop_front(); for (ri i=0;i<4;i++) { int nx=cur.x+dx[i],ny=cur.y+dy[i]; if (g[nx][ny]=='#') continue; int cost; if (g[nx][ny]=='1') cost=1; else cost=0; if (dis[cur.x][cur.y]+cost<dis[nx][ny]) { dis[nx][ny]=dis[cur.x][cur.y]+cost; if (!cost) q.push_front((node){nx,ny,dis[nx][ny]}); else q.push_back((node){nx,ny,dis[nx][ny]}); } } } for (ri i=1;i<=n;i++) for (ri j=1;j<=m;j++) if (dis[i][j]<=d) { if (dist(ii,jj,i,j)>ans) { //cout<<ii<<" "<<jj<<" "<<i<<" "<<j<<endl; ans=dist(ii,jj,i,j); } } } //cout<<ans<<endl; printf("%.6lf",ans); }