思路
- 记录当前位置cx,cy
- 计算去采摘下一个最大值所需要的时间
- 计算从目标最大值是否能回家
- 若上两条满足了,就到最大值处,同时更新当前位置
- 若不满足就退出循环
- 采摘完也要退出循环
参考代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25;
int g[N][N];//路是行为0的线
int n,m,k;
pair<int,int> get_max()
{
int res=0;
int x=0,y=0;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(g[i][j]>res){
x=i;
y=j;
res=g[i][j];
}
}
}
return {x,y};
}
int main()
{
cin>>m>>n>>k;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
cin>>g[i][j];
}
}
int ans=0;//记录答案
int cx=0,cy=0;//记录当前位置
while(1){
//cout<<k<<endl;
auto t = get_max();
int mx=t.first,my=t.second;//目标位置
if(mx==0&&my==0)break;
//cout<<"--"<<g[mx][my]<<endl;
//cout<<"*"<<abs(mx-cx)+abs(my-cy)<<endl;
int x=0;//耗费体力
int hx=0;//回家所需要的体力
if(cx==0){//在路边
x+=mx;
}
else{
x=x+abs(mx-cx)+abs(my-cy);
}
x++;//采摘
hx+=mx;
//cout<<x<<endl;
if(k>=(hx+x)){
k-=x;
ans+=g[mx][my];
cx=mx;
cy=my;
g[mx][my]=0;
}
else{
break;
}
}
cout<<ans<<endl;
return 0;
}