HDU ACM 1078 FatMouse and Cheese 记忆化+DFS[通俗易懂]

HDU ACM 1078 FatMouse and Cheese 记忆化+DFS

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

题意:FatMouse在一个N*N方格上找吃的,每一个点(x,y)有一些吃的,FatMouse从(0,0)的出发去找吃的。每次最多走k步,他走过的位置能够吃掉吃的。保证吃的数量在0-100。规定他仅仅能水平或者垂直走,每走一步。下一步吃的数量须要大于此刻所在位置,问FatMouse最多能够吃多少东西。

须要对步数进行扩展。

#include<iostream>
using namespace std;

#define N 101
#define max(a,b) ((a)>(b)?(a):(b))
int dp[N][N],map[N][N];
int k,n;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

bool ok(int x,int y)         //推断边界
{
	return x>=0 && y>=0 && x<n && y<n;
}

int dfs(int x,int y)              //记忆化搜索
{
	int i,j,max=0,xt,yt,tmp;

	if(dp[x][y]>0)
		return dp[x][y];
	for(i=0;i<4;i++)
		for(j=1;j<=k;j++)
		{
			xt=dir[i][0]*j+x;
			yt=dir[i][1]*j+y;
			if(ok(xt,yt)&&map[x][y]<map[xt][yt])
			{
				tmp=dfs(xt,yt);
				if(tmp>max)            //找到最大的
					max=tmp;
			}
		}
	dp[x][y]=max+map[x][y];
	return dp[x][y];
}

int main()      
{
	int i,j;

	while(scanf("%d%d",&n,&k)==2 && k!=-1 && n!=-1)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				scanf("%d",&map[i][j]);
		memset(dp,0,sizeof(dp));
		cout<<dfs(0,0)<<endl;
	}
    return 0;      
}

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

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

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

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

(0)


相关推荐

  • Futex系统调用,Futex机制,及具体案例分析[通俗易懂]

    Futex系统调用,Futex机制,及具体案例分析[通俗易懂]Futex1、背景1.1自己实现锁1.1.1自旋锁1.1.2sleep+自旋1.1.3小结1.2futex1.2.1什么是Futex1.2.2futex诞生之前1.2.3futex诞生之后2、Futex系统调用3、Futex机制4、具体案例分析4.1在Bionic中的实现4.2C语言实现5、参考及扩展阅读首先要区分一下futex系统调用和futex机制。futex系统调用是操作系统提供给上层的系统调用接口。而futex机制是使用futex接口实现的一种锁。1、背景线程同步可以说

  • 什么是QT[通俗易懂]

    什么是QT[通俗易懂]QT是什么?它能做什么?Qt是一个1991年由QtCompany开发的跨平台C++图形用户界面应用程序开发框架。它既可以开发GUI程序,也可用于开发非GUI程序,比如控制台工具和服务器。简单来说,QT可以很轻松的帮你做带界面的软件,甚至不需要你投入很大精力。QT学习需要避免的坑QT分为4.0版本和5.0版本他们之间的差别很大,不通用!!!不通用!!!不通用!!!所以要么你学习4.0要么你学习5….

  • Sobel算子的理解

    Sobel算子的理解sobel算子主要用于获得数字图像的一阶梯度,常见的应用和物理意义是边缘检测。原理算子使用两个33的矩阵(图1)算子使用两个33的矩阵(图1)去和原始图片作卷积,分别得到横向G(x)和纵向G(y)的梯度值,如果梯度值大于某一个阈值,则认为该点为边缘点Gx方向的相关模板:Gy方向的相关模板:看了网上的很多资料,都把卷积和相关的概念给弄糊了,书上

  • 图集谷-写真集-爬虫-1.0[通俗易懂]

    图集谷-写真集-爬虫-1.0[通俗易懂]图集谷写真集爬虫

  • 股票软件开发

    股票软件开发求助编辑百科名片股票软件开发顾名思义就是股票软件开发公司为公司或个人开发制作自已个性化的股票分析软件,从此彻底告别依赖别人的技术平台支持,从股票软件名称,公司LOGO,启动界面,系统功能,特色指标、特色选股、软件注册后台,信息发布平台,机构数据,主力行情,大盘分析,个股分析,资金分析,热点分析等等一系列功能上实行自已品牌化管理运行。目录

  • html怎么将表格居中_HTML居中代码

    html怎么将表格居中_HTML居中代码表格是一种以有组织的方式呈现大量信息的绝佳方式。销售数据、网页流量、股票市场趋势和学生成绩是经常以表格形式呈现的信息示例。使用HTML将表格添加到网页时,将其置于页面中心可能更具视觉吸引力。居中文本和图片通常是通过text-align类或通过CSS来完成的,但是居中表格需要不同的方法。下面提供了有关如何使表格在网页上居中的详细信息。将表格添加到网页时,默认情况下,它与页面或容器的左侧对齐,如下所示。上表的HTML源代码如下。要使此表居中,您需要添加;margin-left:auto;margin-r

发表回复

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

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