微策略2012年校园招聘笔试题-棋盘寻宝扩展

http://www.acmerblog.com/blog-1243.html
现在有一个8*8的棋盘，上面放着64个不同价值的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于100），一个人初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角。从棋盘的左上角移动到右下角的时候的，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，但是拿到的所有的礼物的价值之和不大于一个限定值limit，请设计一个算法请实现，使其能够获得不超过限制值limit的最大价值的礼物。 

加了限制，这时只能考虑有情况了。这里使用dfs求解，加上剪枝:if (sum > limit) return;

02	int map[8][8], i, j, ans, limit;

03	void f(int x, int y, int sum) {

04	sum += map[x][y];

05	if (sum > limit)

06

return;

07	if (x == 7 && y == 7 && sum > ans)

08	ans = sum;

09	if (x < 7)

10	f(x + 1, y, sum);

11	if (y < 7)

12	f(x, y + 1, sum);

13

}

14

15	int main() {

16	while(~scanf("%d",&limit)) {

17

ans = 0;

18	for(i=0; i<8; i++) {

19	for(j=0; j<8; j++) {

20	scanf("%d",&map[i][j]);

21

}

22

}

23

f(0,0,0);

24	if(ans > 0)

25	printf("%d\n",ans);

26	else puts("-1");

27

}

28

return 0;

29

}