Saturday, June 4, 2016
C++ Solution to UVA 118 - Mutant Flatworld Explorers Learning Based on Experience of Past Robots
June 04, 2016
118
,
2d array using pointers
,
algorithm
,
beginner
,
bound checking
,
character mapping to index
,
commented code
,
cpp
,
easy
,
explanation
,
graph
,
learning from experience
,
Mutant Flatworld Explorers
,
solution
,
uva
Problem Link:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=54Problem Explanation & Visalization:
TODOInput & Output Explanation:
TODOInput & Output:
Input:5 3 1 1 E RFRFRFRF 3 2 N FRRFLLFFRRFLL 0 3 W LLFFFLFLFL
Output:1 1 E 3 3 N LOST 2 3 S
More input and output in udebug:
https://www.udebug.com/UVa/352Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Author: Asif Ahmed | |
| * Site: http://quickgrid.blogspot.com | |
| * Description: 118 - Mutant Flatworld Explorers.cpp | |
| * Write a code so a robot learns from mistakes of past robots. | |
| * The robot doesn't fall off from the location the past robots fell off from. | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define M 4 | |
| static int directions[] = {'N', 'E', 'W', 'S'}; | |
| // Helper function is created to map characters in direction array | |
| // to their index. This can be avoided by using index instead of characters. | |
| static int helper[M]; | |
| // The mapper arrays are mappings from direction array with left right directions. | |
| // They can also be calculated easily using modular arithmetic since they repeat. | |
| /* | |
| | N E W S | |
| ----------- | |
| L | E S N W | |
| R | W N S E | |
| */ | |
| static int Rmapper[] = {'E', 'S', 'N', 'W'}; | |
| static int Lmapper[M]; | |
| // Check all four directions N, E, W, S | |
| // This are values to add to current co-ordinates to see if the current position | |
| // which maybe (x,y) is out of bound or, not. | |
| static int dr[] = {0, 1, -1, 0}; | |
| static int dc[] = {1, 0, 0, -1}; | |
| int main(){ | |
| // | |
| //freopen("input.txt", "r", stdin); | |
| //freopen("output.txt", "w", stdout); | |
| // Fill left mapping array opposite of right since they are inverse of each other | |
| for(int i = 0, j = M - 1; i < M; ++i, --j) | |
| Lmapper[i] = Rmapper[j]; | |
| // Map the directions array characters to their specific index using helper array. | |
| for(int i = 0; i < M; ++i) | |
| helper[ directions[i] ] = i; | |
| int r, c; | |
| scanf("%d%d", &r, &c); | |
| // This is need since the dimension includes (0,0) and (r,c). | |
| ++r, ++c; | |
| // Initialize two dimensional array of terrain. | |
| // This array is not really needed for this problem, but can be used to retrace path. | |
| int** terrain = new int*[r]; | |
| for(int i = 0; i < r; ++i) | |
| terrain[i] = new int[c]; | |
| // Have a data structure to store the co-ordinates where the earlier robots fell off. | |
| // This is a simple learning mechanism where new robots learn from experiences of other robots. | |
| int** scent = new int*[r]; | |
| for(int i = 0; i < r; ++i){ | |
| scent[i] = new int[c]; | |
| for(int j = 0; j < c; ++j) | |
| scent[i][j] = 0; | |
| } | |
| string instructions; | |
| int posX, posY; | |
| char dir; | |
| while( cin >> posX >> posY >> dir >> instructions ){ | |
| // Make all positions unmarked. | |
| for(int i = 0; i < r; ++i) | |
| for(int j = 0; j < c; ++j) | |
| terrain[i][j] = 0; | |
| // Sit in given position with given direction. | |
| terrain[posX][posY] = dir; | |
| bool stopProcessing = false; | |
| // In the left right turn commands just turn to the calculated direction. | |
| // In case of forward command check if the position trying to reach is out of bound. | |
| // If not check if other robots fell off from the same position. | |
| for(int i = 0; instructions[i]; ++i ){ | |
| if( instructions[i] == 'L' ){ | |
| terrain[posX][posY] = Lmapper[ helper[ terrain[posX][posY] ] ]; | |
| } | |
| else if( instructions[i] == 'R'){ | |
| terrain[posX][posY] = Rmapper[ helper[ terrain[posX][posY] ] ]; | |
| } | |
| else{ | |
| int idx = helper[ terrain[posX][posY] ]; | |
| bool outOfBound = ( posX + dr[idx] < 0 || posX + dr[idx] >= r || posY + dc[idx] < 0 || posY + dc[idx] >= c ); | |
| if( outOfBound ){ | |
| if( scent[posX][posY] != 'x' ){ | |
| scent[posX][posY] = 'x'; | |
| printf("%d %d %c LOST\n", posX, posY, terrain[posX][posY]); | |
| stopProcessing = true; | |
| break; | |
| } | |
| }else{ | |
| int prevPosX = posX; | |
| int prevPosY = posY; | |
| posX = posX + dr[idx]; | |
| posY = posY + dc[idx]; | |
| terrain[posX][posY] = terrain[prevPosX][prevPosY]; | |
| terrain[prevPosX][prevPosY] = 0; | |
| } | |
| } | |
| } | |
| if( !stopProcessing ) | |
| printf("%d %d %c\n", posX, posY, terrain[posX][posY]); | |
| } | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment