P1086 花生采摘(搜索dfs)
程序员文章站
2022-07-07 15:48:07
...
这道题我开头没看见题目上说每个点种的花生数目不一样,所以考虑的dfs,写完发现题目所花生数目不一样。。。。。。。。可以直接sort即可就完事儿的;
不过dfs有可能会卡到o(n!)去,但这道题没有卡住;
题意:每次去找最大的花生数目去摘,注意每次走一格和摘是2个单位时间,所以注意时间即可;
dfs思路:把所有MAX找出来,然后搜索所有情况,每次dfs进来说明这个点是可以到的并且能够有剩余时间回去;
AC代码:
#include<bits/stdc++.h>
using namespace std;
struct Node{
int x,y;
int val;
Node(int xx,int yy,int v){
x=xx;y=yy;val=v;
}
};
vector<Node> V;
int m,n,k;
int ans=0;
int book[30][30];//标记数组
void dfs(int xx,int yy,int t,int sum){
int MM=0;
for(int i=0;i<V.size();i++){//找最大值出来
if(!book[V[i].y][V[i].x]){
if(V[i].val>MM){
MM=V[i].val;
}
}
}
int index[40];
int cnt=0;
for(int i=0;i<V.size();i++){
if(V[i].val==MM&&!book[V[i].y][V[i].x]){//找出所有最大的值点
index[cnt++]=i;
}
}
for(int i=0;i<cnt;i++){
int x=V[index[i]].x,y=V[index[i]].y;
if(k-t-(abs(y-yy)+abs(x-xx)+1)>=y+1){
book[y][x]=1;
dfs(x,y,t+abs(y-yy)+abs(x-xx)+1,sum+V[index[i]].val);
book[y][x]=0;
}
}
//能执行到这里说明不能走了
ans=max(ans,sum);//取结果最大值
}
int main(){
scanf("%d %d %d",&m,&n,&k);
int Map[20][20];
int x[25],y[25];
int Max=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&Map[i][j]);
Max=max(Map[i][j],Max);
if(Map[i][j])V.push_back(Node(j,i,Map[i][j]));
}
}
int num=0;
for(int i=0;i<V.size();i++){
if(V[i].val==Max){
x[num]=V[i].x;
y[num++]=V[i].y;
}
}
for(int i=0;i<num;i++){
if(k-y[i]-2>=y[i]+1)//下一个点可以走,并且有足够的时间回去
{
book[y[i]][x[i]]=1;
int sum=Map[y[i]][x[i]];
dfs(x[i],y[i],y[i]+2,sum);
book[y[i]][x[i]]=0;
}
}
printf("%d\n",ans);
return 0;
}
上一篇: 揭秘:吴蜀联盟究竟是怎么被破的?
下一篇: jsonp跨域时出现错误解决记录