棋盘寻宝(微策略2012年校园招聘笔试题)-白红宇

棋盘寻宝(微策略2012年校园招聘笔试题)

阅读量：5062 次

发布时间：2019-06-12

本文共 3299 字，大约阅读时间需要 10 分钟。

题目描述：

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

输入：

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

输出：

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

样例输入：

2 8 15 1 10 5 19 193 5 6 6 2 8 2 1216 3 8 17 12 5 3 1413 3 2 17 19 16 8 712 19 10 13 8 20 16 154 12 3 14 14 5 2 1214 9 8 5 3 18 18 204 2 10 19 17 16 11 3

样例输出：

Code:

#include 
       
        #include 
        
          using namespace std; int go[][2]={    {
      1,0},    {
      0,1}}; int answer;int maze[10][10];vector
         
           value; void DFS(int x,int y){    int sum=0;    if(x==7&&y==7){        vector
          
           ::iterator iter;        for(iter=value.begin();iter!=value.end();++iter){            sum+=*iter;        }        if(sum>answer)            answer=sum;        return;    }    for(int i=0;i<2;++i){        int new_x=x+go[i][0];        int new_y=y+go[i][1];        if(new_x>=8||new_y>=8)            continue;        value.push_back(maze[new_x][new_y]);        DFS(new_x,new_y);        value.pop_back();    }    return;} int main(){    while(cin>>maze[0][0]){        for(int i=1;i<8;++i)            cin>>maze[0][i];        for(int i=1;i<8;++i){            for(int j=0;j<8;++j){                cin>>maze[i][j];            }        }        value.clear();        answer=0;        value.push_back(maze[0][0]);        DFS(0,0);        cout<
           
            <

棋盘寻宝扩展

题目描述：

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

输入：

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

输出：

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

样例输入：

904 2 5 1 3 8 9 74 5 2 3 7 1 8 67 2 1 8 5 9 3 62 8 9 5 6 3 1 71 2 4 5 3 7 9 63 5 7 8 9 6 2 410 8 1 4 7 5 3 97 4 6 2 1 3 9 8

样例输出：

Code:

#include 
         
          #include 
          
            using namespace std; int go[][2]={    {
        1,0},    {
        0,1}}; int answer;bool haveAnswer;int maze[10][10];vector
           
             value; void DFS(int x,int y,int limit){    int sum=0;    if(x==7&&y==7){        vector
            
             ::iterator iter;        for(iter=value.begin();iter!=value.end();++iter){            sum+=*iter;        }        if(sum<=limit){            haveAnswer=true;        }        if(sum>answer&&sum<=limit)            answer=sum;        return;    }    for(int i=0;i<2;++i){        int new_x=x+go[i][0];        int new_y=y+go[i][1];        if(new_x>=8||new_y>=8)            continue;        value.push_back(maze[new_x][new_y]);        DFS(new_x,new_y,limit);        value.pop_back();    }    return;} int main(){    int limit;    while(cin>>limit){        for(int i=0;i<8;++i){            for(int j=0;j<8;++j){                cin>>maze[i][j];            }        }        value.clear();        answer=0;        haveAnswer=false;        value.push_back(maze[0][0]);        DFS(0,0,limit);        if(haveAnswer)            cout<
             
              <

转载于:https://www.cnblogs.com/Murcielago/p/4206690.html

你可能感兴趣的文章