[UVa] 532 - Dungeon Master

With this, I get inside the first 1000 coders on UVa. :)

Submission details:

Submission no: 9461491
Problem no: 532 
Problem title: Dungeon Master
Status: Accepted
Language: C++
Runtime: 0.012
Date of submission: 2011-11-11
Time of submission: 11:12:39

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define INF 9999999
using namespace std;

typedef struct xp
{
    int l, x, y;
} cord;

bool color[100][100][100];
int d[100][100][100];
char inp[100][100][100];

int dirs[10][4]={ {-1,0,0}, {1,0,0}, {0,-1,0}, {0,0,-1}, {0,0,1}, {0,1,0} };

int bfs(cord S, cord E, cord M)
{
    int i, j, k;

    for (i=0 ; i<=M.l+1 ; i++)
    {
        for (j=0 ; j<=M.x+1 ; j++)
        {
            for (k=0 ; k<=M.y+1 ; k++)
            {
                color[i][j][k]=false;
                d[i][j][k]=INF;
            }
        }
    }
    color[S.l][S.x][S.y]=true;
    d[S.l][S.x][S.y]=0;

    cord u, temp;

    queue<cord> q;
    q.push(S);
    while (!q.empty())
    {
        u = q.front();
        q.pop();

        for (i=0 ; i<6 ; i++)
        {
            temp.l = u.l+dirs[i][0];
            temp.x = u.x+dirs[i][1];
            temp.y = u.y+dirs[i][2];

            if (!color[temp.l][temp.x][temp.y] && inp[temp.l][temp.x][temp.y]!='#')
            {
                if (temp.l<1||temp.l>M.l||temp.x<1||temp.x>M.x||temp.y<1||temp.y>M.y)
                    continue;
                color[temp.l][temp.x][temp.y]=true;
                d[temp.l][temp.x][temp.y]=d[u.l][u.x][u.y]+1;
                if (i==E.l && j==E.x && k==E.y) return d[temp.l][temp.x][temp.y];
                    q.push(temp);
            }
        }
    }

    return d[E.l][E.x][E.y];
}


int main()
{
    int l, w, h, i, j, k, res;
    cord S, E, M;
    while (scanf("%d %d %d",&l,&h,&w)==3 && l&&h&&w)
    {
        getchar();

        M.l = l;
        M.x = h;
        M.y = w;

        for (i=1 ; i<=l ; i++)
        {
            for (j=1 ; j<=h ; j++)
            {
                gets(&inp[i][j][1]);
                for (k=1 ; k<=w ; k++)
                {
                    if (inp[i][j][k]=='S')
                    {
                        S.l = i;
                        S.x = j;
                        S.y = k;
                    }
                    if (inp[i][j][k]=='E')
                    {
                        E.l = i;
                        E.x = j;
                        E.y = k;
                    }
                }
            }
            gets(&inp[i][j][1]);
        }

        res = bfs(S,E,M);

        if (res==INF)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n",res);
    }
    return 0;
}

[UVa] 167 - The Sultan's Successors

One thing's for sure, Backtracking is damn fun!!! :D
I liked this one a lot. Though I had to take some help for this one. But it still increased a lot of knowledge about Backtracking.

#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;

bool col[100], d1[100], d2[100];

class c
{
    public:
    int x, y;
};

c crd[100];

int knt=0, board[100][100];

c lst[1000];

int qplace(int n)
{
    if (n>8)
    {
        for (int i=1 ; i<=8 ; i++)
        {
            lst[knt++]=crd[i];
        }
        return 0;
    }
    for (int k=1 ; k<=8 ; k++)
    {
        if (!col[k] && !d1[n+k] && !d2[n-k+8])
        {
            col[k]=d1[n+k]=d2[n-k+8]=true;
            crd[n].x = n;
            crd[n].y = k;
            qplace(n+1);
            col[k]=d1[n+k]=d2[n-k+8]=false;
        }
    }
    return 0;
}

int main()
{
    int test, i, j, sum, max;
    knt = 0;
    for (i=0 ; i<=100 ; i++)
        col[i]=d1[i]=d2[i]=false;
    qplace(1);
    //cout << knt << endl;



    scanf("%d",&test);
    while (test--)
    {
        for (i=1 ; i<=8 ; i++)
        {
            for (j=1 ; j<=8 ; j++)
            {
                scanf("%d",&board[i][j]);
            }
        }
        max = 0;
        for (i=0 ; i<knt ; i+=8)
        {
            for (j=i, sum=0 ; (j-i)<8 ; j++)
            {
                sum += board[lst[j].x][lst[j].y];
            }
            if (sum>max)
                max = sum;
        }
        cout << setw(5) << max << endl;
    }
    return 0;
}

[UVa] 12114 - Bachelor Arithmetic

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ERROR 1e-11
using namespace std;
typedef double dt;

dt min(dt a, dt b)
{
    return (a<b?a:b);
}

int main()
{
    dt s, b, nx_pro, pr_pro;
    int kase=1;

    while (cin >> b >> s)
    {
        if (fabs(b-0.00)<ERROR && fabs(s-0.00)<ERROR) break;

        cout << "Case " << kase++ << ": ";
        pr_pro = min(s/b,(dt)1);
        if (b==1.00)
        {
            cout << ":-\\" << endl;
            continue;
        }
        nx_pro = min((s-(dt)1)/(b-(dt)1),(dt)1);

        if (nx_pro>pr_pro) cout << ":-)" << endl;
        else if (nx_pro<pr_pro) cout << ":-(" << endl;
        else cout << ":-|" << endl;
    }

    return 0;
}

[UVa] 11958 - Coming Home

#include <stdio.h>

int main()
{
    int test, bn, ch, cm, ah, am, dur, i, cur_time, arr_time, min_time, spend, kase=1;
    scanf("%d",&test);

    while (test--)
    {
        min_time = 1000000;

        scanf("%d %d:%d",&bn,&ch,&cm);

        cur_time = ch*60 + cm;

        for (i=0 ; i<bn ; i++)
        {
            scanf("%d:%d %d",&ah,&am,&dur);

            arr_time = ah*60 + am;

            if (arr_time<cur_time) spend = 1440 - cur_time + arr_time + dur;
            else spend = arr_time - cur_time + dur;

            if (min_time>spend) min_time = spend;
        }

        printf("Case %d: %d\n",kase++,min_time);
    }

    return 0;
}

[UVa] 10948 - The Primary Problem

#include <cstdio>
#include <iostream>
using namespace std;
bool ver[10000500];
int sieve()
{
    int i, j, k=0;

    //lst[k++]=2;
    for (i=3 ; i<=10000000 ; i+=2)
    {
        if (!ver[i])
        {
            //lst[k++]=i;
            for (j=3 ; i*j<=10000000 ; j+=2)
            {
                ver[i*j]=true;
            }
        }
    }
    //lst[0]=2;

    return k;
}

int main()
{
    sieve();
    int n, i;
    bool found;

    while (std::cin >> n && n)
    {
        std::cout << n << ":" << std::endl;

        if ((((n-2)&1) && !ver[n-2]) || (n-2 == 2))
        {
            std::cout << "2+" << n-2 << std::endl;
            continue;
        }
        found = false;
        for (i=3 ; i<=((n+1)/2) ; i+=2)
        {
            if (!ver[i] && !ver[n-i] && (n-i)&1)
            {
                std::cout << i << "+" << n-i << std::endl;
                found = true;
                break;
            }
        }
        if (!found) std::cout << "NO WAY!" << std::endl;
    }
    return 0;
}

[UVa] 10391 - Compound Words

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector<string> words;

class kmap
{
    public:
    kmap (const int &v):defVal (v)
    {
    }
    int &getVal(const string &k)
    {
        if (m.find(k) == m.end())
            return defVal;
        else
            return m[k];
    }
    int &operator[] (const string &k)
    {
        return m[k];
    }
    std::map<string,int> m;
    int defVal;
};

kmap ver(-1);

int main()
{
    string word, s1, s2;
    int i, j;

    i=0;
    while (cin >> word)
    {
        words.push_back(word);
        ver[word]=i++;
    }
    int list_len = words.size();

    for (i=0 ; i<list_len ; i++)
    {
        int wlen = words[i].length();
        //cout << words[i] << endl;
        for (j=1 ; j<wlen ; j++)
        {
            s1 = words[i].substr(0,j);
            s2 = words[i].substr(j,wlen);

            //cout << "\t" << ver[s1] << "--" << ver[s2] << endl;

            if (ver.getVal(s1)!=-1 && ver.getVal(s2)!=-1 && ver[s1]!=i && ver[s2]!=i)
            {
                cout << words[i] << endl;
                break;
            }
        }
    }
    return 0;
}

[UVa] 1230 - MODEX

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;

ll sqr(ll v)
{
    return v*v;
}

ll bigMod(ll p, ll v, ll m)
{
    if (p==0) return 1;
    else if (p&1) return (v%m * bigMod(p-1,v,m))%m;
    else return (sqr(bigMod(p/2,v,m)))%m;
}

int main()
{
    int tst;
    ll x, y, n;

    cin >> tst;

    while (tst--)
    {
        cin >> x >> y >> n;
        cout << bigMod(y,x,n) << endl;
    }

    cin >> tst;

    return 0;
}