首页 > 搜索 > BFS搜索 > HDU 2979-Expensive Drink-BFS-[解题报告]HOJ
2014
02-24

HDU 2979-Expensive Drink-BFS-[解题报告]HOJ

Expensive Drink

问题描述 :

There are some water, milk and wine in your kitchen. Your naughty little sister made some strange drinks by mixing them together, and then adds some sugar! She wants to know whether they taste good, but she doesn’t want to try them herself. She needs your help.

Your sister knows that you don’t want to drink them either (anyone wants to?), so she gives you a chance to escape: if you can guess the price of a special drink, she gives you freedom. Warning: she loves her special drink so much that you should never under-estimate its cost! That is, you’re to find the most expensive possible price of it.

The price of each drink equals to its cost. If the amounts of water, milk, wine and sugar used in the drink are a1, a2, a3 and a4 respectively, and the unit costs of water, milk, wine and sugar are c1, c2, c3 and c4 respectively, then the drink costs a1c1 + a2c2 + a3c3 + a4c4 . To give you some hope to win, she told you the costs of exactly n ordinary drinks. Furthermore, she promised that the total cost of sugar a4c4 is always a real number in the interval [L, R] , in any drink.

Sadly, you don’t know the exact price of anything (you’re a programmer, not a housewife!), but you know that water is the cheapest; wine is the most expensive, i.e., 0<=c1<=c2<=c3 . Then the best thing you can do is to assume units costs can be any real numbers satisfying this inequality.

Write a program to find the highest possible price of the special drink.

输入:

The input contains several test cases. The first line of each test case contains three positive integers n, L, R (1<=n<=100, 0<=L<=R<=100) . The next n lines each contain four non-negative integer a1, a2, a3 , p (0<=a1,a2,a3<=100, 0<=p<=10000) , the amount of water, milk and wine, and the price. The last line of the case contains three integers a1, a2, a3 (0<=a1,a2,a3<=100) , the drink to be estimated. The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. The first line of each test case contains three positive integers n, L, R (1<=n<=100, 0<=L<=R<=100) . The next n lines each contain four non-negative integer a1, a2, a3 , p (0<=a1,a2,a3<=100, 0<=p<=10000) , the amount of water, milk and wine, and the price. The last line of the case contains three integers a1, a2, a3 (0<=a1,a2,a3<=100) , the drink to be estimated. The last test case is followed by a single zero, which should not be processed.

样例输入:

1 3 5 
1 2 3 10
2 4 6 
1 2 4 
1 1 1 1
1 1 1 
1 3 8 
0 1 0 17
0 0 1 
3 1 2 
2 1 3 14
1 5 1 15
7 3 2 21
4 1 6 
2 0 2 
45 31 53 4087
30 16 1 1251
11 51 34
0

样例输出:

Case 1: 19.0000 
Case 2: Inconsistent data 
Case 3: Too expensive! 
Case 4: 26.2338 
Case 5: 3440.3088

HOJ 2979 Escape from Pyramids

//题意:按照题中给的金字塔的位置 ,s代表起点 ,*代表障碍,@代表此路可走
//      D代表出口(注意出口不止一个),在规定的时间内判断是否能走出金字塔
//思路:BFS求最短的路径上面所走的步数,注意搜索失败的时候队列是空的,判断一下子
//调试注意:
//  1.注意步数是1这种特殊情况(对应题目中所给样例的case3) 输出的是1 minute 而不是1 minutes
//  2.注意是两个案例之间有空格,最后一个案例后面没有空格
//  3.printf()在很多输出时候就显示出优势来啦,不改啦,下次a题的时候用printf(),cout太恶心啦!
#include<iostream>
#include<cstring>
#include<queue>
#define maxlen  110
using namespace std;
struct node
{
    int x,y,step;
};
int mat[maxlen][maxlen];
int dir[6][2]= {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1}};
int BFS(node s,node e[],int count,int m)
{
    int i;
    queue<node> q;
    node ol,ne;//旧的状态和新的状态
    while(!q.empty())
    {
        q.pop();
    }//建立空队列
    s.step=0;
    q.push(s);//搜索起点入队
    mat[s.x][s.y]=1;
    while(!q.empty())
    {
        ol=q.front();
        q.pop();
        for(i=0; i<count; i++)
        {
            if(ol.x==e[i].x&&ol.y==e[i].y)
              {
                  return ol.step;
              }
        }//搜索到出口,直接返回,因为是BFS,故最先搜索到的尾最小
        for(i=0; i<6; i++)
        {
            ne.x=ol.x+dir[i][0];
            ne.y=ol.y+dir[i][1];
            ne.step=ol.step;
            if(!(ne.x>=0&&ne.y>=0&&ne.x<m&&ne.y<m&&ne.y<=ne.x&&!mat[ne.x][ne.y]))
                  continue;
            else
            {
                mat[ne.x][ne.y]=1;
                ne.step++;
                q.push(ne);
            }
        }
    }
    if(q.empty())return -1;//搜索失败
    else return ne.step;
}
int main()
{
    node s,e[maxlen];//出口有可能不止一个,设数组
    int m,n,N=0,tem=0,i,j,count,minl;
    char k;
    while(cin >>m >>n)
    {
        if(tem==1) cout << endl;
        tem=1;//两个样例之间有一空格,最后一个样例后面没有
        count=0;
        memset(mat,0,sizeof(mat));
        N++;//样例的个数
        for (i=0; i<m; i++)
        {
            for (j=0; j<=i; j++)
            {
                cin>> k;
                if(k=='S')
                {
                    s.x=i;
                    s.y=j;
                }
                else if(k=='*')  mat[i][j]=1;//不能走
                else if(k=='D')
                {
                    e[count].x=i;
                    e[count].y=j;
                    count++;//出口的个数
                }
                else  mat[i][j]=0;//可以走
            }
        }
        minl=BFS(s,e,count,m);
        if(minl>1&&minl<=n)  cout << "Maze #" << N << " :" <<  endl << "Hurry up, You need " << minl << " minutes to escape!" << endl ;
        else if(minl==1&&minl<=n)  cout <<"Maze #" << N <<  " :" << endl <<  "Hurry up, You need 1 minute to escape!" << endl;
          else  cout << "Maze #" << N << " :" <<  endl <<"Oh No, I'm afraid that you don't have enough time to escape!" << endl ;
        //注意1的情况,恶心啦一天啊
    }
    return 0;
}

下面发一下林2B的代码,确实写得不错:

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;
bool vis[101][101];
char map[101][101];
int dx[]= {-1,-1,0,0,1,1};
int dy[]= {-1,0,-1,1,0,1};
int T,n;
struct point
{
    int x,y,t;
};
int main()
{
    char c;
    int cases=1;
    int tmp=0;
    while(scanf("%d%d",&n,&T)==2)
    {
        if(tmp==1)  printf("\n");
        tmp=1;
        memset(vis,false,sizeof(vis));
        point start;
        queue<point> v;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=i; j++)
            {
                scanf(" %c",&c);
                map[i][j]=c;
                if(c=='S')
                {
                    start.x=i;
                    start.y=j;
                    start.t=0;
                    vis[i][j]=true;
                }
            }
        }
        v.push(start);
        int ans=10000000;
        while(!v.empty())
        {
            point cur,pre;
            pre=v.front();
            if(map[pre.x][pre.y]=='D')
            {
                ans=pre.t;
                break;
            }
            v.pop();
            for(int i=0; i<6; i++)
            {
                cur.x=pre.x+dx[i];
                cur.y=pre.y+dy[i];
                if(cur.x>0&&cur.x<=n&&cur.y>0&&cur.y<=cur.x&&!vis[cur.x][cur.y]&&map[cur.x][cur.y]!='*')
                {
                    cur.t=pre.t+1;
                    vis[cur.x][cur.y]=true;
                    v.push(cur);
                }
            }
        }
        printf("Maze #%d :\n",cases++);
        if(ans>T) printf("Oh No, I'm afraid that you don't have enough time to escape!\n");
        else if(ans==1)   printf("Hurry up, You need 1 minute to escape!\n");
        else printf("Hurry up, You need %d minutes to escape!\n",ans);
    }
    return 0;
}

解题参考:http://blog.csdn.net/hit1110310422/article/details/8543302


,