时光机TimeMachine

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
const int N = 30+5;
const int S[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int n,m,t;
short map[N][N],dis[N][N],v[N][N],ind[N][N];
double ans;
int calc(int x,int y){return (x-1)*(m) + y;}
queue<pair<int,int> >dui;
int main(){
	//freopen("in.txt","r",stdin);
	int i,j,k;
	n = scan();m = scan();t = scan();
	char cc;
	for(i=0;i<=n+1;i++)
	for(j=0;j<=m+1;j++)
		map[i][j] = 1;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			scanf(" %c",&cc);
			if(cc=='1')map[i][j] = 1;
			else map[i][j] = 0;
		}
	ans = 0;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++){
		//pre-set
		int code = calc(i,j);
		while(!dui.empty())dui.pop();
		dui.push(pair<int,int>(i,j));
		if(map[i][j])dis[i][j] = 1;
		else dis[i][j] = 0;
		v[i][j] = code;
		ind[i][j] = 1;
		//cut1
		if(dis[i][j] > t)continue;
		//cut2
		bool ok;
		if(map[i][j]==0)ok=0;
		else ok = 2;
		for(k=0;k<4&&ok==0;k++){
			int x,y;x = i+S[k][0];y = j+S[k][1];
			if(map[x][y])ok=1;
		}
		//spfa
		if(!ok)continue;
		while(!dui.empty()){
			pair<int,int> now = dui.front();dui.pop();
			for(k=0;k<4;k++){
				int x,y;
				x = now.first+S[k][0];y = now.second+S[k][1];
				if(!(1<=x&&x<=n&&1<=y&&y<=m))continue;
				if(v[x][y]!=code||dis[x][y] > dis[now.first][now.second] + map[x][y]){
					dis[x][y] = dis[now.first][now.second] + map[x][y];
					v[x][y] = code;
					if(dis[x][y] > t)continue;
					else ans = max(ans,hypot(fabs(x-i),fabs(y-j)));
					if(!ind[x][y]){
						ind[x][y] = 1;
						dui.push(pair<int,int>(x,y));
					}
				}
			}
			ind[now.first][now.second]=0;
		}
	}
	printf("%.6f\n",ans);
	return 0;
}