首页 > ACM题库 > 九度OJ > 九度-1529-棋盘寻宝[解题代码]
2013
12-13

九度-1529-棋盘寻宝[解题代码]

题目来源:微策略2012年校园招聘笔试题

题目描述:

现在有一个8*8的棋盘,上面放着64个价值不等的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0小于1000),一个人的初始位置在棋盘的左上角,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,结束位置在棋盘的右下角,请设计一个算法使其能够获得最大价值的礼物。

输入:

输入包含多个测试用例,每个测试用例共有8行8列,第i行的第j列的数字代表了该处棋盘上的礼物的价值,每两个数之间用空格隔开。

输出:

对于每组测试用例,请输出你能够获得最大价值的礼物。

样例输入:
2 8 15 1 10 5 19 19
3 5 6 6 2 8 2 12
16 3 8 17 12 5 3 14
13 3 2 17 19 16 8 7
12 19 10 13 8 20 16 15
4 12 3 14 14 5 2 12
14 9 8 5 3 18 18 20
4 2 10 19 17 16 11 3
样例输出:
194

cpp 代码如下:
#include <stdio.h>
int map[8][8], i, j, ans;
int main() {
	while(~scanf("%d",&map[0][0])) {
		for(j=1; j<8; j++) {
			scanf("%d",&map[0][j]);
			map[0][j] += map[0][j-1];
		}
		for(i=1; i<8; i++) {
			scanf("%d",&map[i][0]);
			map[i][0] += map[i-1][0];
			for(j=1; j<8; j++) {
				scanf("%d",&map[i][j]);
				map[i][j] += (map[i][j-1] > map[i-1][j] ? map[i][j-1]:map[i-1][j]);
			}
		}
		printf("%d\n",map[7][7]);
	}
	return 0;
}
/**************************************************************
	Problem: 1529
	User: coder
	Language: C
	Result: Accepted
	Time:0 ms
	Memory:912 kb
****************************************************************/


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }