uva : 532 - Dungeon Master

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include < cstdio > #include < queue > using namespace std; char dungeon[32][32][32]; int Distance[32][32][32]; int L, R, C; const int direction[6][3] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 1, 0 }, { 0, 0, -1 }, { 0, 0, 1 } }; struct point_type { int x; int y; int z; }; int BFS(int i, int j, int k) { Distance[i][j][k] = 0; queue < point_type > q; q.push(point_type { i, j, k }); dungeon[i][j][k] = '#'; point_type cur, nxt; while (!q.empty()) { cur = q.front(); q.pop(); for (int i = 0; i < 6; ++i) { nxt.x = cur.x + direction[i][0]; nxt.y = cur.y + direction[i][1]; nxt.z = cur.z + direction[i][2]; if (nxt.x < 0 || nxt.x >= L || nxt.y < 0 || nxt.y >= R || nxt.z < 0 || nxt.z >= C) continue; if (dungeon[nxt.x][nxt.y][nxt.z] != '#') { Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1; if (dungeon[nxt.x][nxt.y][nxt.z] == 'E') return Distance[nxt.x][nxt.y][nxt.z]; dungeon[nxt.x][nxt.y][nxt.z] = '#'; q.push(nxt); } } } return -1; } int main() { while (scanf("%d%d%d", & L, & R, & C)) { if (!L && !R && !C) break; int start_i, start_j, start_k; for (int i = 0; i < L; ++i) { for (int j = 0; j < R; ++j) { scanf("%s", dungeon[i][j]); for (int k = 0; k < C; ++k) if (dungeon[i][j][k] == 'S') { start_i = i; start_j = j; start_k = k; } } } int minute = BFS(start_i, start_j, start_k); if (minute != -1) printf("Escaped in %d minute(s).\n", minute); else printf("Trapped!\n"); } return 0; }

uva : 531 - Compromise

#include<stdio.h>
#include<string.h>
char a[200][200],b[200][200];
int length1=0,length2=0;
int table[200][200],s[200][200],flag=0;

void lcsprint(int length1,int length2)
{
    if(length1==0||length2==0)return;
    if(s[length1][length2]==1)
    {
        lcsprint(length1-1,length2-1);
        if(flag==0)printf("%s",a[length1]);
        else printf(" %s",a[length1]);
        flag=1;
    }
    else if(s[length1][length2]==2)
    {
        lcsprint(length1-1,length2);
    }
    else lcsprint(length1,length2-1);
}

void lcs()
{
    int i,j,k,l,m,n;
    for(i=0;i<=length1;i++)
    {
        for(j=0;j<=length2;j++)table[i][j]=0;
    }
    for(i=1;i<length1;i++)
    {
        for(j=1;j<length2;j++)
        {
            if(strcmp(a[i],b[j])==0)
            {
                table[i][j]=table[i-1][j-1]+1;
                s[i][j]=1;
            }
            else if(table[i-1][j]>=table[i][j-1])
            {
                table[i][j]=table[i-1][j];
                s[i][j]=2;
            }
            else
            {
                table[i][j]=table[i][j-1];
                s[i][j]=3;
            }
        }
    }
    lcsprint(length1-1,length2-1);

}

int main()
{
    char temp[1000];
    while(scanf("%s",&temp)==1)
    {
        flag=0;
        length1=1,length2=1;
        strcpy(a[length1++],temp);
        while(scanf("%s",&temp))
        {
            if(strcmp(temp,"#")==0)break;
            strcpy(a[length1++],temp);
        }
        while(scanf("%s",&temp))
        {
            if(strcmp(temp,"#")==0)break;
            strcpy(b[length2++],temp);
        }
        lcs();
        printf("\n");
    }
    return 0;
}

uva : 530 - Binomial Showdown

#include<stdio.h>
int main()
{
    long n,m;
    while(scanf("%ld %ld",&n,&m)==2)
    {
        if(n==0&&m==0)
           break;
        else if(n==0&&m==1)
        {
            printf("1\n");
        }
        else{
        long  num1[1000],lnum1=1,i,j,k,l,r=0,div[1000],ldiv=0;
        long sum=1;
        num1[0]=1;
        l=n-m;
        if(l<m)
        {
            for(i=m+1;i<=n;i++)
            {
                for(j=0;j<lnum1;j++)
                {
                    k=(num1[j]*i+r)%10;
                    r=(num1[j]*i+r)/10;
                    num1[j]=k;
                }
                while(r!=0)
                {
                    num1[lnum1++]=r%10;
                    r=r/10;
                }
            }
            for(i=2;i<=l;i++)
            {
                sum=sum*i;
            }
        }
        else
        {
            for(i=l+1;i<=n;i++)
            {
                for(j=0;j<lnum1;j++)
                {
                    k=(num1[j]*i+r)%10;
                    r=(num1[j]*i+r)/10;
                    num1[j]=k;
                }
                while(r!=0)
                {
                    num1[lnum1++]=r%10;
                    r=r/10;
                }
            }
            for(i=2;i<=m;i++)
            {
                sum=sum*i;
            }
        }
        j=0;k=0;
        for(i=lnum1-1;i>=0;i--)
        {
            k=(num1[i]+r*10)/sum;
            r=(num1[i]+r*10)%sum;
            if(k>0)
            {
                j=1;
            }
            if(j==1)
            {
                div[ldiv++]=k;
            }
        }
        for(i=0;i<ldiv;i++)
        {
            printf("%ld",div[i]);
        }printf("\n");
    }
    }
    return 0;
}