UVa : 10116


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#define For(a) for ( i = 0; i < a; i++ )
#define Rep(a, b) for ( i = a; i <= b; i++ )
#define N 1000000
using namespace std;

int row;
int column;
int enter;
char grid [1000] [1000];
bool visited [1000] [1000];
int steps;
int steps_b4_stuck;
int stuck;

void function ()
{
    steps = stuck = steps_b4_stuck = 0;

    for ( int i = 0; i < 1000; i++ ) {
        for ( int j = 0; j < 1000; j++ )
            visited [i] [j] = false;
    }

    int enter_x = 0;
    int enter_y = enter - 1;

    while ( enter_x >= 0 && enter_x < row && enter_y >= 0 && enter_y < column ) {
        if ( visited [enter_x] [enter_y] == true )
            break;

        visited [enter_x] [enter_y] = true;

        if ( grid [enter_x] [enter_y] == 'N' )
            enter_x--;

        else if ( grid [enter_x] [enter_y] == 'S' )
            enter_x++;

        else if ( grid [enter_x] [enter_y] == 'E' )
            enter_y++;

        else if ( grid [enter_x] [enter_y] == 'W' )
            enter_y--;

        steps++;

    }

    if ( visited [enter_x] [enter_y] == false )
        return;

    steps = 0;

    int x = 0;
    int y = enter - 1;

    while ( x != enter_x || y != enter_y ) {
        if ( grid [x] [y] == 'N' )
            x--;

        else if ( grid [x] [y] == 'S' )
            x++;

        else if ( grid [x] [y] == 'E' )
            y++;

        else if ( grid [x] [y] == 'W' )
            y--;

        steps_b4_stuck++;
    }

    x = enter_x;
    y = enter_y;

    do {
        if ( grid [x] [y] == 'N' )
            x--;

        else if ( grid [x] [y] == 'S' )
            x++;

        else if ( grid [x] [y] == 'E' )
            y++;

        else if ( grid [x] [y] == 'W' )
            y--;

        stuck++;
    } while ( x != enter_x || y != enter_y );

}

int main ()
{
    while ( scanf ("%d %d %d", &row, &column, &enter) ) {
        if ( row == 0 && column == 0 && enter == 0 )
            break;

        for ( int i = 0; i < row; i++ )
            scanf ("%s", grid [i]);

        function ();

        if (steps)
            printf ("%d step(s) to exit\n", steps);
        else
            printf ("%d step(s) before a loop of %d step(s)\n", steps_b4_stuck, stuck);


    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

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