AcWing 418. 花生采摘
原题链接
简单
作者:
静夜思离愁
,
2024-02-18 21:03:00
,
所有人可见
,
阅读 26
dfs的解法
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int a[N][N],m,n,k,ans;
void dfs(int x,int y,int t)
{
int mx=-1e9,nx,ny;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>mx)
{
mx=a[i][j];
nx=i,ny=j;
}
if(y==0)y=ny;
int nt=abs(nx-x)+abs(ny-y)+nx+1; //采摘最大值并返回路边的总时间
if(t<nt||!a[nx][ny])return;
else
{
ans+=a[nx][ny];
a[nx][ny]=0;
dfs(nx,ny,t-nt+nx);
}
}
int main()
{
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(0,0,k);
cout<<ans;
return 0;
}