ACM (UVa) : 532


#include <iostream>
#include <queue>
using namespace std;

struct node {
    int row;
    int column;
    int level;
    int color;
    int value;
    char ch;
} a [35] [35] [35];

int l, r, c;
queue <node> q;

void reset ()
{
    for ( int i = 0; i < 35; i++ ) {
        for ( int j = 0; j < 35; j++ ) {
            for ( int k = 0; k < 35; k++ ) {
                a [i] [j] [k].row = j;
                a [i] [j] [k].column = k;
                a [i] [j] [k].level = i;
                a [i] [j] [k].ch = '#';
                a [i] [j] [k].color = 0;
                a [i] [j] [k].value = 99999;
            }
        }
    }
}

void input ()
{
    for ( int i = 1; i <= l; i++ ) {
        for ( int j = 1; j <= r; j++ ) {
            for ( int k = 1; k <= c; k++ )
            cin >> a [i] [j] [k].ch;
        }
    }
}

void find_S ()
{
    for ( int i = 1; i <= l; i++ ) {
        for ( int j = 1; j <= r; j++ ) {
            for ( int k = 1; k <= c; k++ ) {
                if ( a [i] [j] [k].ch == 'S' ) {
                    a [i] [j] [k].value = 0;
                    q.push (a [i] [j] [k]);
                    return;
                }
            }
        }
    }
}

void bfs ()
{
    a [q.front().level] [q.front().row] [q.front().column].color = 2;

    int tempL;
    int tempR;
    int tempC;

    /* north */
    tempL = q.front ().level;
    tempR = q.front ().row - 1;
    tempC = q.front ().column;

    if ( tempR > 0 && a [tempL] [tempR] [tempC].color == 0 && a [tempL] [tempR] [tempC].ch != '#' ) {
		a [tempL] [tempR] [tempC].value = a [q.front ().level] [q.front ().row] [q.front ().column].value + 1;
		a [tempL] [tempR] [tempC].color = 1;
		q.push (a [tempL] [tempR] [tempC]);
	}

	/* south */
	tempL = q.front ().level;
    tempR = q.front ().row + 1;
    tempC = q.front ().column;

    if ( tempR <= r && a [tempL] [tempR] [tempC].color == 0 && a [tempL] [tempR] [tempC].ch != '#' ) {
		a [tempL] [tempR] [tempC].value = a [q.front ().level] [q.front ().row] [q.front ().column].value + 1;
		a [tempL] [tempR] [tempC].color = 1;
		q.push (a [tempL] [tempR] [tempC]);
	}

	/* east */
	tempL = q.front ().level;
    tempR = q.front ().row;
    tempC = q.front ().column - 1;

    if ( tempC > 0 && a [tempL] [tempR] [tempC].color == 0 && a [tempL] [tempR] [tempC].ch != '#' ) {
		a [tempL] [tempR] [tempC].value = a [q.front ().level] [q.front ().row] [q.front ().column].value + 1;
		a [tempL] [tempR] [tempC].color = 1;
		q.push (a [tempL] [tempR] [tempC]);
	}

	/* west */
	tempL = q.front ().level;
    tempR = q.front ().row;
    tempC = q.front ().column + 1;

    if ( tempC <= c && a [tempL] [tempR] [tempC].color == 0 && a [tempL] [tempR] [tempC].ch != '#' ) {
		a [tempL] [tempR] [tempC].value = a [q.front ().level] [q.front ().row] [q.front ().column].value + 1;
		a [tempL] [tempR] [tempC].color = 1;
		q.push (a [tempL] [tempR] [tempC]);
	}

	/* up */
	tempL = q.front ().level + 1;
    tempR = q.front ().row;
    tempC = q.front ().column;

    if ( tempL <= l && a [tempL] [tempR] [tempC].color == 0 && a [tempL] [tempR] [tempC].ch != '#' ) {
		a [tempL] [tempR] [tempC].value = a [q.front ().level] [q.front ().row] [q.front ().column].value + 1;
		a [tempL] [tempR] [tempC].color = 1;
		q.push (a [tempL] [tempR] [tempC]);
	}

	/* down */
	tempL = q.front ().level - 1;
    tempR = q.front ().row;
    tempC = q.front ().column;

    if ( tempL > 0 && a [tempL] [tempR] [tempC].color == 0 && a [tempL] [tempR] [tempC].ch != '#' ) {
		a [tempL] [tempR] [tempC].value = a [q.front ().level] [q.front ().row] [q.front ().column].value + 1;
		a [tempL] [tempR] [tempC].color = 1;
		q.push (a [tempL] [tempR] [tempC]);
	}

    a [q.front ().level] [q.front().row] [q.front().column].color = 2;
	q.pop ();
}

void find_E ()
{
    for ( int i = 1; i <= l; i++ ) {
        for ( int j = 1; j <= r; j++ ) {
            for ( int k = 1; k <= c; k++ ) {

                if ( a [i] [j] [k].ch == 'E' && a [i] [j] [k].value < 99999 ) {
                    printf ("Escaped in %d minute(s).\n", a [i] [j] [k].value);
                    return;
                }
            }
        }
    }

    printf ("Trapped!\n");
}



int main ()
{
    while ( cin >> l >> r >> c && l && r && c ) {

        reset ();
        input ();
        find_S ();

        while ( !q.empty () ) {

            if ( a [q.front().level] [q.front().row] [q.front().column].color != 2)
            bfs ();
        }

        find_E ();
/*
        for ( int i = 1; i <= l; i++ ) {
            for ( int j = 1; j <= r; j++ ) {
                for ( int k = 1; k <= c; k++ )
                    printf ("%d ", a [i] [j] [k].value);
                printf ("\n");
            }
            printf ("\n");
        }
*/
    }

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s