UVALive 5066 Fire Drill

java-mans

浏览: 11710516 次

最近访客更多访客>>

morelily

devcang

serisboy

chjinniu

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (15567)

社区版块

存档分类

2012-08 ( 1467)
2012-07 ( 1872)
2012-06 ( 1125)
更多存档...

Description

Joko is taking part in a fire drill which is held by the Jakarta Fire Department to recruit new firemen. The drill is about rescuing volunteers (who act as unconscious people) trapped in a building in a limited time. The building has several floors, and the volunteers are scattered throughout the building. Each volunteer has points assigned to her. The fireman candidate should rescue volunteers through carrying them to the exit. The candidate will earn the assigned points for each volunteer he rescued.

Each floor of a building can be seen as a grid of cells. Each cell can be an obstacle, an empty space, a stair or an entry/exit point.

A candidate starts at the entry point which exists only at one single cell of the first floor of the building. The candidate can move to any adjacent non-obstacle cells (north, south, west or east) or climb up or down a stair in 1 second. The movement slows down to 2 seconds when the candidate carries a volunteer. When a candidate finds a volunteer, he may decide to rescue her or not, but if he decides to rescue her, he has to carry her back to the exit without stopping. He can only carry at most one volunteer at a time.

Joko has the floor plan of the test building. Help him plan his moves, so he can get the highest possible score.

Input

The first line of input contains an integerT(T $\le$ 100)denoting the number of case. Each case has five integersL(1 $\le$ L $\le$ 10),H(1 $\le$ H $\le$ 100),W(1 $\le$ W $\le$ 100),N(1 $\le$ N $\le$ 100)andS(1 $\le$ S $\le$ 10, 000)denoting the number of floors, height and weight of each floor, the number of unconscious people, and the given time respectively.

The nextLblocks describe the map of each floor from the 1st floor to theL-th floor respectively. Each floor consists ofHlines each containsWcharacters. Characters that may appear in each floor are:

``S" : The starting point, also serves as the exit point. There will be only one starting/exit point and it will appear in the first floor.
``X" : Obstacle, cell that cannot be visited (wall, fire, etc.).
``U" : Stair that connect to the upper floor. There will be a ``D" character at the same place in the upper level. This character will not appear in the highest level of the building.
``D" : Stair that connect to the lower floor. There will be a ``U" character at the same place in the lower level. This character will not appear in the lowest level of the building.
``." : Empty space, cell that can be visited.

The nextNlines each contains four integersf_i(1 $\le$ f_i $\le$ L),r_i(1 $\le$ r_i $\le$ H),c_i(1 $\le$ c_i $\le$ W),p_i(1 $\le$ p_i $\le$ 1, 000)denoting the location of each volunteer (floor, row, column) and the point assigned to this volunteer respectively. You can assume that each volunteer will be located in empty space and no two volunteer occupy the same location.

Output

For each case, output in a line a single integer the highest point that he can earn by rescuing unconscious people within the given time.

Sample Input

2 
3 3 5 3 55 
XXXXX 
X..UX 
XSXXX 
XXXXX 
XU.DX 
XXXXX 
XXXXX 
XD..X 
XXXXX 
1 2 3 10 
3 2 3 50 
3 2 4 60 
2 2 6 4 27 
...... 
S..U.. 
...... 
...D.. 
1 2 3 20 
1 2 5 50 
1 2 6 50 
2 1 1 90

Sample Output

110 
100

题目描述：救人，这是一个三维的迷宫着火了，里面有若干人，时间一定，一次只能救一人，且从出发点到被救的人那里的时间是回来的时间的一半，救一个人获得P「i」的价值，问你最多能得到多少价值；

我想到的方法是从起点开始进行宽度优先遍历，把救每个人的最短时间求出来，然后再来次01背包就可以解决了。

LANGUAGE:C++

CODE:

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 101
using namespace std;

struct node
{
    int x,y,z,step;
};

const int dir[4][3]= {{0,1,0},{0,0,1},{0,-1,0},{0,0,-1}};
char matrix[11][101][101];
int height,width,length;
int v,path[101],p[101],f[10001];

bool check(int x,int y,int z)
{
    if(x>-1&&y>-1&&z>-1&&x<height&&y<width&&z<length)
        return 1;
    return 0;
}
void bfs(int startx,int starty,int startz)
{
    queue <node>que;
    node cur,next;
    bool used[maxn][maxn][maxn]={{{0}}};
    int pcnt=0;
    int tx,ty,tz;

    cur.x=startx,cur.y=starty,cur.z=startz,cur.step=0;
    used[cur.x][cur.y][cur.z]=1;
    que.push(cur);

    while(!que.empty())
    {
        cur=que.front();que.pop();
        if(matrix[cur.x][cur.y][cur.z]=='&')
        {
            path[pcnt++]=cur.step;
        }
        if(matrix[cur.x][cur.y][cur.z]=='U')
        {
            tx=cur.x+1;
            if(tx<height&&matrix[tx][cur.y][cur.z]!='X'&&!used[tx][cur.y][cur.z])
            {
                next.x=tx,next.y=cur.y,next.z=cur.z,next.step=cur.step+1;
                used[next.x][next.y][next.z]=1;
                que.push(next);
            }
        }
        else if(matrix[cur.x][cur.y][cur.z]=='D')
        {
            tx=cur.x-1;
            if(tx>-1&&matrix[tx][ty][tz]!='X'&&!used[tx][cur.y][cur.z])
            {
                next.x=tx,next.y=cur.y,next.z=cur.z,next.step=cur.step+1;
                used[next.x][next.y][next.z]=1;
                que.push(next);
            }
        }
        for(int i=0;i<4;i++)
        {
            tx=cur.x+dir[i][0],ty=cur.y+dir[i][1],tz=cur.z+dir[i][2];
            if(check(tx,ty,tz)&&!used[tx][ty][tz]&&matrix[tx][ty][tz]!='X')
            {
                used[tx][ty][tz]=1;
                next.step=cur.step+1,next.x=tx,next.y=ty,next.z=tz;
                que.push(next);
            }
        }
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    int tCase,volun,x,y,z;
    int sx,sy,sz;
    scanf("%d",&tCase);
    getchar();
    while(tCase--)
    {
        scanf("%d%d%d%d%d",&height,&width,&length,&volun,&v);
        getchar();
        for(int i=0; i<height; i++)
        {
            for(int j=0; j<width; j++)
            {
                for(int k=0; k<length; k++)
                {
                    scanf("%c",&matrix[i][j][k]);
                    if(matrix[i][j][k]=='S')
                    {
                        sx=i,sy=j,sz=k;
                    }
                }
                matrix[i][j][length]='\0';
                getchar();
            }
        }
        for(int i=0; i<volun; i++)
        {
            scanf("%d%d%d%d",&x,&y,&z,&p[i]);
            matrix[x-1][y-1][z-1]='&';
        }
        bfs(sx,sy,sz);
        memset(f,0,sizeof(f));
        for(int i=0;i<volun;i++)
        path[i]*=3;
        for(int i=0;i<volun;i++)
        {
            for(int j=v;j>=path[i];j--)
            {
                f[j]=max(f[j],f[j-path[i]]+p[i]);
            }
        }
        printf("%d\n",f[v]);
    }
    return 0;
}

分享到：