FatMouse and Cheese 想不通，其实是很简单的一道搜索题，怎么说是题目分类时分到动规那一组，害得我做死的想动规怎么做 还搞得我想了两天。用搜索不到一个小时搞定：不过，在我思路比较乱的情况下做的，所以这样搜也不是最优的。不管了，先贴出来再说： a[][]记录每格的食物数量。max[][]记录从i,j搜时能吃到最多的食物数量。mark[][]记录当前结点是否在本次搜索过。flag[][]记录的是i,j,结点是否已经进行过一次深搜！！！！ #include<stdio.h>int a[103][103];int max[103][103],k,n;int mark[103][103];int flag[103][103];int d[4][2]={{-1,0},{1,0},{0,1},{0,-1}};int DFS(int i,int j); int main(){    int i,j;    while(scanf("%d%d",&n,&k)!=EOF)    {        if(n==-1&&k==-1) break;        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)            {                scanf("%d",&a[i][j]);                max[i][j]=a[i][j];    flag[i][j]=0;    mark[i][j]=0;            } // MAX=0;  mark[1][1]=1;        max[1][1]=DFS(1,1);              printf("%d\n",max[1][1]);    }    return 0;} int DFS(int i,int j){    int kk,dd,dt,st;  int temp;//可以跳K步。 if(flag[i][j]==1) {  return max[i][j]; }    for(dd=0;dd<4;dd++)    {        for(kk=1;kk<=k;kk++)        {            st=i+d[dd][0]*kk;            dt=j+d[dd][1]*kk;            if(st>=1&&st<=n&&dt>=1&&dt<=n )   {    if(a[i][j]<a[st][dt]&&mark[st][dt]==0)    {    // if(max[i][j])     mark[st][dt]=1;     temp=DFS(st,dt);     if(temp+a[i][j]>max[i][j])     {      max[i][j]=temp+a[i][j];     }     mark[st][dt]=0;    }   }   else break;  }            } flag[i][j]=1; return max[i][j];}  

评论