男神的约会

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/65

Description

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

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

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

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

wij 千克的蛋糕，Gorwin从左上角(1,1)的格子开始走，走到右下角(n,m)的格子。在每一步中，Gorwin可以向右或者向下走，即是：Gorwin 站在(i,j)的时候，她可以走向(i+1,j)或者(i,j+1) (然而她不能走出这个花园)。当Gorwin到达一个格子的时候，她可以把那个格子里面的蛋糕吃完或者不吃。但是，她不能只吃一部分。她的胃不是那么大，所以她最多只能吃K千克的蛋糕。现在，Gorwin站在左上角，她在看蛋糕园的地图，想要找出一条路，能够使得她吃到的蛋糕最多的一条路。请你来帮帮忙。

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

HINT

题意

题解：

把这道题当成bfs做，在自己的struct里面，记录自己拿卷的情况

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <ctime>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

struct node

{

    int x,y;

    int v[];

    int step;

    int ans;

};

int g[][];

queue<node>q;

int dx[]={,};

int dy[]={,};

int main()

{

    int n=,m=;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            g[i][j]=read();

    node now;

    memset(now.v,,sizeof(now.v));

    now.x=,now.y=;

    now.step=g[][];

    now.v[g[][]]=;

    now.ans=;

    q.push(now);

    int ans=inf;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        if(now.x==&&now.y==&&now.ans==)

        {

            int flag=;

            ans=min(ans,now.step);

            continue;

        }

        for(int i=;i<;i++)

        {

            node next=now;

            next.x+=dx[i];

            next.y+=dy[i];

            if(next.x<||next.y<||next.y>||next.x>)

                continue;

            int p=g[next.x][next.y];

            next.step+=p;

            if(!next.v[p])

            {

                next.v[p]=;

                next.ans++;

            }

            q.push(next);

        }

    }

    cout<<ans<<endl;

}

男神