hdu 1078 FatMouse and Cheese (dfs+记忆化搜索)

hdu 1078 FatMouse and Cheese (dfs+记忆化搜索)

大家好,又见面了,我是全栈君。

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4811    Accepted Submission(s): 1945




Problem Description
FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he’s going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse — after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move. 

 


Input
There are several test cases. Each test case consists of 

a line containing two integers between 1 and 100: n and k 

n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) … (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), … (1,n-1), and so on. 

The input ends with a pair of -1’s. 

 


Output
For each test case output in a line the single integer giving the number of blocks of cheese collected. 

 


Sample Input
   
   
3 1 1 2 5 10 11 6 12 12 7 -1 -1

 


Sample Output
   
   
37

 

题意是说每次能够走(1~K)个在同一直线的位置,即不能拐弯走。

数组较大,用记忆化搜索

(类似于poj1088滑雪)

#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"stack"
#include"algorithm"
using namespace std;
#define N 105
#define max(a,b) (a>b?a:b)
int g[N][N],n,k;
int h[N][N];
int dir[4][2]={0,1,0,-1,-1,0,1,0};
int judge(int x,int y)
{
    if(x<0||x>=n||y<0||y>=n)
        return 0;
    return 1;
}
int dfs(int x,int y)
{
    if(h[x][y])
        return h[x][y];
    int i,j,u,v,t,sum=0,s1;
    t=g[x][y];
    for(i=0;i<4;i++)
    {
        for(j=1;j<=k;j++)
		{
			u=x+dir[i][0]*j;
            v=y+dir[i][1]*j;
            if(judge(u,v)&&g[u][v]>t)
            {
                s1=dfs(u,v);
                sum=max(sum,s1);
            }
		}
    }
    return h[x][y]=g[x][y]+sum;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&k),n!=-1||k!=-1)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&g[i][j]);
                h[i][j]=0;
            }
        }

        int ans=dfs(0,0);
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115377.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • windows 开机自动登录并锁定「建议收藏」

    windows 开机自动登录并锁定「建议收藏」首先来看看系统启动自动登录的设置:  按住Win键,再按R键(Win+R),启动”运行”窗口;  WindowsXP/2003/2008/2008R2输入”controluserpasswords2″(不含引号)回车;  Windows7输入”netplwiz”(不含引号),回车;  在”用户帐户”-“用户”界面中,取消”要使用本机,用户必须输入用户名和密码(E)”复选框;  按”确定”按钮

  • 雅典娜暴利烹饪系列(下)「建议收藏」

    雅典娜暴利烹饪系列(下)「建议收藏」”呀–呀–呀–“爬到冰箱上的纱织吓的花容失色,”快点把那些土鳖拿开啦—-“端着一盆螃蟹的迪马斯头上好几个”加号”:”你叫个什么劲呀!!!不是你要学煮螃蟹,叫我下河给你捞的吗?!!这是螃蟹!!!螃蟹!!!!”纱织眼睛里无辜的泪水在打转:”骗人!螃蟹明明是红色的~~~””那是煮熟的好不好!!!”迪马斯已经在昏倒的边缘,”快拿去!!!””不要呀~~~~好可怕呀~~~~~”玉手一挥,螃蟹

  • grahphics_blitz

    grahphics_blitz1.前言Graphics的Blit方法是比较简单也是比较常用的方法。最简单的作用是将一张纹理绘制到另一张纹理中。而在此方法中可以指定一种材质来实现特殊的效果,所以常和OnRenderImage方法配

  • Vue props用法小结[通俗易懂]

    Vue props用法小结[通俗易懂]Vue props用法小结

  • 冒泡排序详解_超详细电音

    冒泡排序详解_超详细电音1、什么是冒泡排序?冒泡排序的英文BubbleSort,是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。冒泡排序的原理:每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位,第二趟只能将倒数第2位上的数归位,依次类推下去。如果有n个数进行排序,只需将n-1个数归位,也就是要进行n-1趟操作。而“每一趟”都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面

    2022年10月19日
  • WSUS Troubleshooting guide「建议收藏」

    WSUS Troubleshooting guide「建议收藏」TroubleshootingguideforissueswhereWSUSclientsarenotreportingin来自于WSUSTEAMBLOGThisguideiswrittentoassistspecificallyintroubleshootingWSUSwhenclientsarenotrepor…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号