C++14(g++5.4) 解法, 执行用时: 276ms, 内存消耗: 492K, 提交时间: 2020-09-28 15:33:50

#include<bits/stdc++.h>
using namespace std;
#define maxn 40
int n,m,t,lmax;
float l;
char c;
int a[maxn][maxn];
int v[maxn][maxn];
int xx[4] = {0,0,-1,1};
int yy[4] = {1,-1,0,0};
void dfs(int x,int y,int z){
    if(x < 0 || y < 0 || x > n-1 || y > m-1) return ;
    if(z>=v[x][y]) return;
    if(z>t) return;
	v[x][y] = z;
    for(int i=0;i<4;i++){
        int nx=xx[i]+x;
        int ny=yy[i]+y;
		dfs(nx,ny,z+a[nx][ny]);
    }
}
int main(){
	cin>>n>>m>>t;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++) 
        cin>>c,a[i][j]=c-'0';
     for(int i=0;i<n;i++){
    	for(int j=0;j<m;j++){ 
    			memset(v,0x3f,sizeof(v));
    			dfs(i,j,a[i][j]);
	    		for(int q=0;q<n;q++){
	    			for(int w=0;w<m;w++){
	    				if(v[q][w]<=t){
	    					lmax=max(lmax,(q-i)*(q-i)+(w-j)*(w-j));
	    				}		
	    			}
	    		}	
		}
	}	
   printf("%.6lf\n",sqrt(lmax));
}

C++11(clang++ 3.9) 解法, 执行用时: 461ms, 内存消耗: 396K, 提交时间: 2020-09-28 22:28:13

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int dir[4][2]={-1,0,1,0,0,-1,0,1};
int ans;
int dis[N],mp[N];
int n,m,t;
string tmpstr[50];
void dfs(int pos,int sum){
	if(sum>t) return ;
	if(sum>=dis[pos]) return ;
	dis[pos]=sum;
	for(int k=0;k<4;k++){
		int tx=pos/m+dir[k][0],ty=pos%m+dir[k][1];
		if(tx<0 || tx>=n || ty<0 || ty>=m) continue;
		dfs(tx*m+ty,sum+mp[tx*m+ty]);		
	}
}

int main(){
	cin>>n>>m>>t;
	for(int i=0;i<n;i++) cin>>tmpstr[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			mp[i*m+j]=tmpstr[i][j]-'0';
		}
	
	int B=(n-1)*m+(m-1);
	for(int i=0;i<=B;i++){
		memset(dis,0x3f3f3f3f,sizeof dis);
		dfs(i,mp[i]);
		for(int j=0;j<=B;j++){
			if(dis[j]<=t) ans=max(ans,(i/m-j/m)*(i/m-j/m)+(i%m-j%m)*(i%m-j%m));
		}
	}
	printf("%.6lf\n",sqrt(ans));
}