UVa : 11705 (Grasshopper)



// http://uva.onlinejudge.org/external/117/11705.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int Row, Col;
char output [50 + 3] [50 + 3];
int mat [50 + 3] [50 + 3];

struct trampoline {
	int r;
	int c;
	int cost;
} a [50 + 3] [50 + 3], p;

void reset ()
{
	for ( int i = 0; i < 53; i++ ) {
		for ( int j = 0; j < 53; j++ ) {
			a [i] [j].r = i;
			a [i] [j].c = j;
			a [i] [j].cost = INT_MAX;
		}
	}

	memset (output, 'X', sizeof (output));
	output [0] [0] = '*';
}

char direction ( char curr, int r, int c, int r1, int c1 )
{
	if ( curr == '*' || curr == 'N' ) return curr;
	
	char new_curr;

	if ( r < r1 ) new_curr = 'S';
	else if ( r > r1 ) new_curr = 'N';
	else if ( c < c1 ) new_curr = 'E';
	else new_curr = 'W';

	if ( curr == 'X' ) return new_curr;

	char *str = "NWES";
	char *curr_pos = strchr (str, curr);
	char *new_pos = strchr (str, new_curr);

	if ( curr_pos > new_pos ) return new_curr;
	return curr;
}

int main ()
{
	while ( scanf ("%d %d", &Row, &Col) ) {
		if ( Row == 0 && Col == 0 ) break;

		reset ();

		for ( int i = 0; i < Row; i++ ) {
			for ( int j = 0; j < Col; j++ ) scanf ("%d", &mat [i] [j]);
		}

		queue <trampoline> q;

		// push every cell of first row with cost = 1
		for ( int i = 1; i < Col; i++ ) {
			if ( mat [0] [i] == i ) {
				a [0] [i].cost = 1;
				output [0] [i] = 'W';
				q.push (a [0] [i]);
			}
		}

		// push every cell of first column with cost = 1
		for ( int i = 1; i < Row; i++ ) {
			if ( mat [i] [0] == i ) {
				a [i] [0].cost = 1;
				output [i] [0] = 'N';
				q.push (a [i] [0]);
			}
		}

		while ( !q.empty () ) {
			p = q.front ();
			q.pop ();

			for ( int i = 0; i < Col; i++ ) {
				if ( abs (p.c - i) == mat [p.r] [i] && a [p.r] [i].cost > p.cost + 1 ) {
					a [p.r] [i].cost = p.cost + 1;
					output [p.r] [i] = direction ( output [p.r] [i], p.r, i, p.r, p.c );
					q.push (a [p.r] [i]);
				}
				else if ( abs (p.c - i) == mat [p.r] [i] && a [p.r] [i].cost == p.cost + 1 ) {
					output [p.r] [i] = direction (output [p.r] [i], p.r, i, p.r, p.c );
				}
			}

			for ( int i = 0; i < Row; i++ ) {
				if ( abs (p.r - i) == mat [i] [p.c] && a [i] [p.c].cost > p.cost + 1 ) {
					a [i] [p.c].cost = p.cost + 1;
					output [i] [p.c] = direction ( output [i] [p.c], i, p.c, p.r, p.c );
					q.push (a [i] [p.c]);
				}
				else if ( abs (p.r - i) == mat [i] [p.c] && a [i] [p.c].cost == p.cost + 1 ) {
					output [i] [p.c] = direction ( output [i] [p.c], i, p.c, p.r, p.c );
				}
			}
		}

		for ( int i = 0; i < Row; i++ ) {
			for ( int j = 0; j < Col; j++ ) printf ("%c", output [i] [j]);
			printf ("\n");
		}

		printf ("\n");
	}

	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