微策略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

分析：

依旧是一个动态规划中的数塔问题，思路比较简单，给出转移方程:

if(i!=7&&j!=7)

	board[i][j]=a[i][j]+max{board[i][j+1],board[i+1][j]}

else

	board[i][7]=a[i][7]+board[i+1][7] ; board[7][j]=a[7][j]+board[7][j+1];

#include<stdio.h>
int a[8][8]={0};
int board[8][8]={0};
 
int main(){
    int i, j;
    while(scanf("%d",&a[0][0])!=EOF){
        for(i=0;i<8;++i)//读取数据
            for(j=0;j<8;++j)
                if(i||j)
                    scanf("%d",&a[i][j]);
        for(i=0;i<8;++i){//初始化记录板
            for(j=0;j<8;++j)
                board[i][j]=0;
        }
        board[7][7]=a[7][7];
        for(i=6;i>=0;--i){
            board[i][7]=a[i][7]+board[i+1][7];
            board[7][i]=a[7][i]+board[7][i+1];
        }
        for(i=6;i>=0;--i){
            for(j=6;j>=0;--j){
                board[i][j]= a[i][j] + (board[i+1][j] > board[i][j+1] ?  board[i+1][j] : board[i][j+1]);
            }
        }       
        printf("%d\n",board[0][0]);
    }
    return 0;
}