bfs-白红宇

bfs

阅读量：4683 次

发布时间：2019-06-09

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

有一天陈世进约了唐威豪去看电影，电影院有一个活动，给你一个10*10的矩阵，每一个格子上都有一个0-9的整数，表示一共十种优惠券中的一种。

观众从左上角的格子开始走，走到右下角。每走到一个有着a号优惠券的格子，都必须要玩一个a分钟的游戏来领取这张优惠券。

每次只能向右或向下走。当走到右下角的时候，如果集齐10种优惠券就可以半价看电影呢。

为了能在唐威豪面前展示自己的才智，陈世进准备用最少的时间领取全部的优惠券(他要省出最多的时间陪唐威豪)。聪明的你能告诉陈世进，他最少要花费的时间是多少？

Input

输入包含10行，每行10个数字，以空格隔开，表示格子上的优惠券的种类。数据保证存在合法路径。

Output

输出陈世进走到右下角的最小时间花费。

Sample Input

0 1 2 3 4 5 6 7 8 91 1 1 1 1 1 1 1 1 02 1 1 1 1 1 1 1 1 03 1 1 1 1 1 1 1 1 04 1 1 1 1 1 1 1 1 05 1 1 1 1 1 1 1 1 06 1 1 1 1 1 1 1 1 07 1 1 1 1 1 1 1 1 08 1 1 1 1 1 1 1 1 09 1 1 1 1 1 1 1 1 5

Sample Output

#include 
     
      using namespace std;#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include 
                
                 #include 
                 
                  int dir[2][2]={ 0,1,1,0};int a[12][12];struct coordinate{ int x; int y; int time; int sign[11];}s;int main(){ for(int i=1;i<=10;i++) for(int j=1;j<=10;j++){ cin>>a[i][j]; } s.time=a[1][1]; memset(s.sign,0,sizeof(s.sign)); s.sign[a[1][1]]=1; queue
                  
                   q; s.x=1; s.y=1; q.push(s); int min1=1e8; while(!q.empty()){ int temp=1; for(int i=0;i<10;i++){ if(q.front().sign[i]==0){ temp=0; break; } } if(temp&&q.front().x==10&&q.front().y==10) min1=min(min1,q.front().time); for(int i=0;i<2;i++){ s=q.front(); s.x=q.front().x+dir[i][0]; s.y=q.front().y+dir[i][1]; s.sign[a[s.x][s.y]]=1; s.time=q.front().time+a[s.x][s.y]; if(s.x<=10&&s.x>0&&s.y>0&&s.y<=10){ q.push(s); } } q.pop(); } cout<
                   
                    <

注意叠加思想

注意边界

转载于:https://www.cnblogs.com/carry-2017/p/7395946.html

你可能感兴趣的文章