乍看还以为是个搜索,dfs都打好了,用个样例一输出发现不对,这第二个样例我输出的时间比较长大概花了几秒钟,并且这还不是最大规模,于是重新读题,然后发现似乎可以用贪心来做注释见代码
#include <bits/stdc++.h>
using namespace std;
int n,m,k,top;
int ans;
int mp[200][200];
struct g{
int x,y,peanut;
bool operator<(const g&rhs)const{
return peanut>rhs.peanut;
}
}a[500];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
if(mp[i][j])
{
a[top].x = i;
a[top].y=j;
a[top++].peanut = mp[i][j];//放进数组
}
}
}
sort(a,a+top);//列个优先级
int sum=0,wast=0;
int x=-1,y=a[0].y;//选个好位置
int wx,wy;
for(int i=0;i<top;i++)
{
wast = 0;
wx = a[i].x;
wy = a[i].y;
wast = abs(x-wx)+abs(y-wy);
/* cout<<wast<<endl; */
//测试用的
k--;
k-=wast;
if(k>=wx+1)//如果时间够就拿花生
{
ans+=mp[wx][wy];
x = wx;
y = wy;
/* cout<<ans<<k<<endl; */
}
else{//不够就直接输出这个解
cout<<ans<<endl;
return 0;
}
}
cout<<ans;
return 0;
}