| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 533 人关注过本帖, 1 人收藏
标题:本题为2011年ACM大赛题目,回溯问题。希望大家给多点关于这题的资料。
只看楼主 加入收藏
cnycompany
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2011-12-11
结帖率:0
收藏(1)
 问题点数:0 回复次数:0 
本题为2011年ACM大赛题目,回溯问题。希望大家给多点关于这题的资料。
题目10:一条贪吃的蛇在一个n*m的网格中游走,它只能从一个方格走向另一个相邻的方格,这里相邻的意思是两个方格有公共边。每个方格可以看作是一个房间,其中一些是空的,一些存放有苹果。贪吃的蛇根本不进入空的房间,而进入有苹果的房间后就可以带走所有苹果使房间成为空的。蛇从一个指定的房间出发,最终回到它的家,把一路带来的苹果存储到家中,当然,它希望带来的苹果最多。请编写程序,输入有整数n和m,及n*m的一个矩阵,矩阵元素数值中有一个是 -1,表示蛇的出发位置,有一个是 -2,表示蛇的家的位置,其余数值是非负整数,0表示房间为空,非零整数表示苹果的数目。输出蛇选择的游走路径和获得的最多的苹果数目。例如输入4*4矩阵:
 7   0   4  18
4   0   1   1
15   7  11   -1
 0  12  -2   0
则应输出 (2, 3), (1, 3), (0, 3), (0, 2), (1, 2), (2, 2), (2, 1), (3, 1), (3, 2), 带回苹果数为1+18+4+1+11+7+12 = 54。(本题为2011年ACM大赛题目)。(可查阅:吕国英,任瑞征等编著,算法设计与分析(第2版),清华大学出版社,2009年1月,第200-202页。
提示:这是一个利用回溯算法的迷宫搜索类型问题,可参考类似问题的已有解法。

搜索更多相关主题的帖子: 苹果 编写程序 资料 
2012-03-09 19:15
快速回复:本题为2011年ACM大赛题目,回溯问题。希望大家给多点关于这题的资料。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015166 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved