当前位置：首页 > news >正文

bfs

news 来源：原创 2024/5/20 5:16:18

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

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

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

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

Input

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

Output

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

Sample Input

0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5

Sample Output

#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
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<coordinate>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<<min1<<endl;
}