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)


相关推荐

  • 谷歌与火狐Hackbar插件下载与安装

    谷歌与火狐Hackbar插件下载与安装谷歌与火狐Hackbar插件下载与安装首先下载Hackbar插件:https://github.com/Mr-xn/hackbar2.1.3将其中的压缩包拖拽到Chrome的扩展程序。点击详细信息在下面的“来源”处点击一个链接:会跳转到给插件在Chrome中安装的文件位置,打开hackbar-panel.js文件将三处disable_hackbar()函数替换成init(),保…

  • 编码风格:Mvc模式下SSM环境,代码分层管理

    编码风格:Mvc模式下SSM环境,代码分层管理

    2020年11月20日
  • qpython3安装pygame_详解Python pygame安装过程笔记

    qpython3安装pygame_详解Python pygame安装过程笔记今天看到一个教程,是关于Python安装pygame模块的。觉得很好,拿来分享一下。安装Python额,这个小题貌似在这里很是多余啊。但是为了照顾到刚刚学习Python的童鞋,我还是多啰嗦两句吧。具体如下:我们要到Python官网。去下载我们需要的版本。我这里下载的是windows64位的Python2.7msi。安装的过程如果不懂,选择为默认即可。安装easy_install至于这是个什么东…

  • WPF Visifire.Charts4.6.1使用教程 附含源码

    WPF Visifire.Charts4.6.1使用教程 附含源码原因:前段时间,公司项目中用到Visifire.Charts4.5.6控件,项目中要求随时可以控制动画效果,用于在大屏上面展示,很酷炫。过程:但是没有源码,于是写了一个方法用动画去控制数量动态增长,无奈效率太低,多实例几个Chart就卡到爆,放弃。没有源码,怎么办呢,无奈之下反编译了一下dll,刚开始用reflector反编译,发现编译出来的大部分都用不了。然后又用ILSpy反编译…

  • 加密Excel解密

    加密Excel解密excel文件进行加密,能够保护excel文件的内容,但是有时候我们自己设置的密码,时间久了可能会忘记,或者在网上下载的excel文件或者同事之间转发的excel文件也有加密,这对于我们来说都不是很方便了。想要解密excel文件的加密,需要用到奥凯丰EXCEL解密大师excel加密有两种,它们的解密方法也是不一样的。激活成功教程打开密码,激活成功教程它的方法目前只有通过软件找到正确密码才能进行解密,所以点击进入【找回密码】,选择一种找回方法进行激活成功教程(如果对自己设置的密码还有一些印象,可以使用组合破击..

  • goland 激活3月最新在线激活

    goland 激活3月最新在线激活,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

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

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