您的位置:澳门402永利com > 编程应用 > 数字三角形

数字三角形

发布时间:2019-09-23 20:45编辑:编程应用浏览(130)

    Dungeon Master
    Time Limit:1000MS Memory Limit:65536K
    Total Submissions:48605 Accepted:18339

    Description

    You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

    Is an escape possible? If yes, how long will it take?

    Input

    The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
    L is the number of levels making up the dungeon.
    R and C are the number of rows and columns making up the plan of each level.
    Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.

    Output

    Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
    Escaped in x minute.

    where x is replaced by the shortest time it takes to escape.
    If it is not possible to escape, print the line
    Trapped!

    Sample Input

    3 4 5S.....###..##..###.#############.####...###########.#######E1 3 3S###E####0 0 0

    Sample Output

    Escaped in 11 minute.Trapped!

    Source

    Ulm Local 1997

    难题呈报

    小Hi和小Ho在经验了招潮蟹先生的天职之后被嘉奖了三次出国观景的机会,于是他们过来了大洋彼岸的U.S.。美利哥匹夫的生活特别风趣,平时会有美妙绝伦、奇离奇怪的活动开设,那不,小Hi和小Ho刚刚下飞机,就赶上了本地的迷宫节活动。迷宫节里展览出来的迷宫都特地的珠璧交辉,然则小Ho却相中了一个事实上并不怎么像迷宫的迷宫——因为那些迷宫的嘉勉特别丰盛~

    于是小Ho找到了小Hi,让小Hi帮忙她收获尽大概多的奖状,小Hi把手一伸道:“迷宫的牵线拿来!”

    小Ho选取的迷宫是三个被称之为“数字三角形”的n(n不超过200)层迷宫,那么些迷宫的第i层有i个屋企,分别编号为1..i。除去最终一层的屋家,每一个房间都会有一对通向下一层的房间的阶梯,用符号来表示的话,正是从第i层的编号为j的房间出发会有两条路,一条通往第i+1层的数码为j的房屋,另一条会朝着第i+1层的号子为j+1的房间,而最终一层的兼具房间都独有一条离开迷宫的征途。那样的征程都是单向的,也正是说当沿着这个道路前往下一层的屋家照旧离开迷宫之后,小Ho没有艺术另行回到这么些屋企。迷宫里还要只会有二个参与者,而在每种加入者步向这一个迷宫的时候,每个房子里都会变卦一定数量的彩票,那一个彩票能够在经过迷宫之后兑换各样奖品。小Ho的源点在第1层的号码为1的房屋,以往小Ho悄悄向另外参与者弄精晓了各类室内的彩票的数量量,希望小Hi帮她妄图出他最多能得到多少奖券。

    提拔一:盲目贪心不可取,寻找计算太耗费时间

    唤醒二:纪念深搜逞神威,宽度优先解难题

    升迁三:总括归纳提公式,收缩冗余是真理

    题意:给您多个多维的迷宫,问能否得以从源点走到顶点,可从前后不断层数,也得以东北西南走,都以一秒二个单位,能够到终端就输出步数,不可以就输出那句话

    输入

    各类测验点(输入文件)有且只有一组测量试验数据。

    每组测验数据的率先行事二个正整数n,表示那一个迷宫的层数。

    接下去的n行描述这么些迷宫中各种房子的奖券数,在那之中第i行的第j个数代表着迷宫第i层的数码为j的房屋中的奖券数量。

    测量试验数据保险,有百分之百的多寡知足n不超过100

    对此百分之百的数额,迷宫的层数n不超越100

    对此百分百的数码,每一种房间中的奖券数不当先一千

    对于百分之五十的数额,迷宫的层数不当先15(小Ho表示2^15才3万多呢,也等于说……)

    对此百分之十的数量,迷宫的层数不超过1(小Hi很诡异你的疆界景况管理的哪些?~)

    对于10%的数额,迷宫的布局满意:对于五分之四之上的结点,左侧道路通向的房子中的奖券数比侧边道路通向的屋家中的奖券数要多。

    对于百分之十的多少,迷宫的组织满足:对于八成以上的结点,左侧道路通向的房子中的奖券数比侧边道路通向的房子中的奖券数要少。

    思路:其实和常见的二维迷宫差不离,正是多了二个层数,相当于多了多个趋势

    输出

    对此每组测量检验数据,输出三个整数Ans,表示小Ho能够获得的最多奖券数。

    样例输入

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

    样例输出

    28
    
    再复习一次基础的动态规划
    
     1 #include <iostream>
     2 #include <algorithm>
     3 #include <cstring>
     4 #include <cstdio>
     5 #include <vector>
     6 #include <cstdlib>
     7 #include <iomanip>
     8 #include <cmath>
     9 #include <ctime>
    10 #include <map>
    11 #include <set>
    12 #include <queue>
    13 using namespace std;
    14 #define lowbit(x) (x&(-x))
    15 #define max(x,y) (x>y?x:y)
    16 #define min(x,y) (x<y?x:y)
    17 #define MAX 100000000000000000
    18 #define MOD 1000000007
    19 #define pi acos(-1.0)
    20 #define ei exp(1)
    21 #define PI 3.141592653589793238462
    22 #define INF 0x3f3f3f3f3f
    23 #define mem(a) (memset(a,0,sizeof(a)))
    24 typedef long long ll;
    25 ll gcd(ll a,ll b){
    26     return b?gcd(b,a%b):a;
    27 }
    28 bool cmp(int x,int y)
    29 {
    30     return x>y;
    31 }
    32 const int N=10005;
    33 const int mod=1e9+7;
    34 int a[101][101];
    35 int main()
    36 {
    37     int n,i,j;
    38     cin>>n;
    39     mem(a);
    40     cin>>a[1][1];
    41     for(i=2;i<=n;i++){
    42         for(j=1;j<=i;j++){
    43             cin>>a[i][j];
    44             a[i][j]=max(a[i-1][j-1],a[i-1][j])+a[i][j];
    45         }
    46     }
    47     sort(a[n],a[n]+n+1);
    48     cout<<a[n][n]<<endl;
    49     return 0;
    50 }
    
    #include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<cstdlib>#include<queue>#include<set>#include<vector>using namespace std;#define INF 0x3f3f3f3f#define eps 1e-10#define PI acos#define ll long longint const maxn = 35;const int mod = 1e9 + 7;int gcd(int a, int b) {    if (b == 0) return a;  return gcd(b, a % b);}char map[maxn][maxn][maxn];int vis[maxn][maxn][maxn];int k,n,m,sx,sy,sz,ex,ey,ez;int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};struct node{    int x,y,z,step;};int check (int x,int y,int z){    if(x<0 || y<0 || z<0 || x>=k || y>=n || z>=m)        return 1;    else if(map[x][y][z]=='#')        return 1;    else if(vis[x][y][z])        return 1;    return 0;}int bfs(){    node a,next;    queue<node>que;    a.x=sx;  a.y=sy;  a.z=sz;    a.step=0;    vis[sx][sy][sz]=1;    que.push;    while(!que.empty    {        a=que.front();        que.pop();        if(a.x == ex && a.y == ey && a.z == ez)            return a.step;        for(int i=0;i<6;i++)        {            next=a;            next.x=a.x+dir[i][0];            next.y=a.y+dir[i][1];            next.z=a.z+dir[i][2];            if(check(next.x,next.y,next.z))                continue;            vis[next.x][next.y][next.z]=1;            next.step=a.step+1;            que.push;        }    }    return 0;}int main(){    while(~scanf("%d %d %d",&k,&n,&m))    {        if(k==0 && n==0 && m==0)            break;        for(int i=0;i<k;i++)        {            for(int j=0;j<n;j++)            {                scanf("%s",map[i][j]);                for(int r=0;r<m;r++)                {                    if(map[i][j][r]=='S')                    {                        sx=i;sy=j;sz=r;                    }                    else if(map[i][j][r]=='E')                    {                        ex=i;ey=j;ez=r;                    }                }            }        }        memset(vis,0,sizeof;        int ans;        ans=bfs();        if            printf("Escaped in %d minute.n",ans);        else            printf("Trapped!n");    }    return 0;}
    

    本文由澳门402永利com发布于编程应用,转载请注明出处:数字三角形

    关键词:

上一篇:没有了

下一篇:没有了