UVA – 10116 – Robot Motion

  • Problem Statement : UVA – 10116 – Robot Motion
  • Type : Simulation, Recursion, DFS
  • Optimization Hint : I used the same board representation as the destination store and visited flagging, assuming that we start with an offset distance OFFSET=256 that will indicate weather the current node is an unvisited node that contains an int within the limit of the char, so we will use the map to get it’s matching array. or it’s a visited node so we subtract the offset getting the absolute distance from the start position.
  • Other Solutions :
#include <iostream>
#include <map>
#include <string.h>
#include <assert.h>
#include <stdio.h>
using namespace std;
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); (ii)++)
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)
#define OFFSET 256
int i, j, I, J,C, Nth[]={-1,+0}, Sth[]={+1,0}, Est[]={0,+1}, Wst[]={0,-1};

map<int, int*> m;
int g[1000][1000];

void go(int y, int x, int d){
	assert(y>=0 && x>=0 && y<I && x<J);
	assert(g[y][x]<OFFSET);

	int y2 = y+m[g[y][x]][0], x2=x+m[g[y][x]][1];	// new co-ordinates
	g[y][x] = d;	// fill with distance, mark as visited; d is always > OFFSET in visited nodes

	if(y2<0 || x2<0 || y2>=I || x2>=J) // Exiting the Board
		printf("%d step(s) to exit\n", d-OFFSET+1);
	else if(g[y2][x2] >= OFFSET) // Visited Node
		printf("%d step(s) before a loop of %d step(s)\n", g[y2][x2] -OFFSET, d - g[y2][x2]+1);
	else go(y2, x2, d+1); // Normal Node
}

int main() {

	char c;
	m['N'] = Nth, m['S'] = Sth, m['E'] = Est, m['W'] = Wst;
	while((cin >> I >> J >> C) && I){
		memset(g, 0, sizeof g);
		FOR2d(i, j, 0, 0, I, J)
		{cin >> c; g[i][j]=c; }
		go(0, C-1, OFFSET);
	}
	return 0;
}
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

%d bloggers like this: