题目链接

https://ac.nowcoder.com/acm/problem/20270

解题思路

暴力枚举+dfs赋值
枚举起点和终点，dis存起点到终点要推的箱子数；dis通过dfs更新

AC代码

#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];//表示当前点到达i位置最少需要推多少箱子 
int mp[N];
int n,m,t;
string tmpstr[50];
void dfs(int pos,int sum){//sum表示要推的箱子数
    if(sum>t) return ;//剪枝1 
    if(sum>=dis[pos]) return ;//剪枝2 
    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]);//确定从此时起点到其他点要推的最小箱子数，赋值给dis
        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));
}