首页 > 搜索 > 回溯和剪枝 > 微策略2012年校园招聘笔试题-棋盘寻宝扩展
2013
11-25

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

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

输入:
输入包含多个测试用例,每个测试用例共有9行,第一行是一个限制值limit<=1000,下面还有8行8列,第i行的第j列的数字代表了该处棋盘上的礼物的价值,每两个数之间用空格隔开。 

输出:
对于每组测试用例,请输出你能够获得不超过限制值limit的最大价值的礼物。若没有符合条件的线路则输出-1。 

样例输入:
90
4 2 5 1 3 8 9 7
4 5 2 3 7 1 8 6
7 2 1 8 5 9 3 6
2 8 9 5 6 3 1 7
1 2 4 5 3 7 9 6
3 5 7 8 9 6 2 4
10 8 1 4 7 5 3 9
7 4 6 2 1 3 9 8
样例输出:
90

加了限制,这时只能考虑所有情况了。这里使用dfs求解,加上剪枝:

if (sum > limit) return;

#include <stdio.h>
int map[8][8], i, j, ans, limit;
void f(int x, int y, int sum) {
	sum += map[x][y];
	if (sum > limit)
		return;
	if (x == 7 && y == 7 && sum > ans)
		ans = sum;
	if (x < 7)
		f(x + 1, y, sum);
	if (y < 7)
		f(x, y + 1, sum);
}

int main() {
	while(~scanf("%d",&limit)) {
		ans = 0;
		for(i=0; i<8; i++) {
			for(j=0; j<8; j++) {
				scanf("%d",&map[i][j]);
			}
		}
		f(0,0,0);
		if(ans > 0)
		printf("%d\n",ans);
		else puts("-1");
	}
	return 0;
}

 


  1. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  2. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  3. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  4. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  5. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  6. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  7. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给

  8. 作者你从一开始就在挖坑为毛要有两个男主呢,到最后了到底是谁呢,是十月的话对不起喜欢琉星,是琉星吧对不起喜欢十月的,作者可是机智啊直接跳了过去让粉丝自己想出自己喜欢的结局谁都对得起,所以说作者真是太机智了。所以大家不要骂作者了,作者不是也承诺我们在单行本给