Problem Link: Robot Path Decoding.
I recently was trying to solve the above-mentioned problem and came up with a stack (std :: stack<std :: pair <int, int>>
) based solution where I am storing the two information regarding the commands during paring i.e. how many times the last command is going to repeat and what is the start index of the repeating command.
But I am getting TLE on submission, so can anyone help me out on how can I optimise the solution or other alternative ways of solving the problem?
Solution Source-Code In C++
#include <iostream>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cstdio>
typedef unsigned long long ull_t;
typedef long long ll_t;
#define FAST_IO(value) std :: ios :: sync_with_stdio(value); std :: cin.tie(NULL)
#define MOD 1000000007 // Constant (prime number) used in most competitive programming problems to reduce the answer to a 32-bit integer.
#define PI 3.141592653589793 // Number of digits(15) of Pi which JPL uses for Interplanetary Caculations.
#define GOLDEN_RATIO 1.618033988749895 // Number of digits(15).
static void move_robot(std :: pair <int, int> &, const char);
static void compute_final_location(std :: pair <int, int> &, const std :: string);
int main(void) {
FAST_IO(0);
int test;
std :: cin >> test;
for(int t = 1; t <= test; ++t) {
std :: pair <int, int> robot_loc = {1, 1};
std :: string command;
std :: cin >> command;
compute_final_location(robot_loc, command);
std :: cout << "Case #" << t << ": " << robot_loc.first << " " << robot_loc.second << std :: endl;
}
return 0;
}
static void move_robot(std :: pair <int, int> & robot_loc, const char direction) {
switch(direction) {
case 'N': {
robot_loc.second -= 1;
}
break;
case 'S': {
robot_loc.second += 1;
}
break;
case 'E': {
robot_loc.first += 1;
}
break;
case 'W': {
robot_loc.first -= 1;
}
break;
}
if(robot_loc.first > 1e9) {
robot_loc.first = 1;
} else if(robot_loc.first < 1) {
robot_loc.first = 1e9;
}
if(robot_loc.second > 1e9) {
robot_loc.second = 1;
} else if(robot_loc.second < 1) {
robot_loc.second = 1e9;
}
}
static void compute_final_location(std :: pair <int, int> & robot_loc, const std :: string command) {
std :: stack <std :: pair <int, int>> repeat_command;
for(size_t i = 0; i < command.size(); ++i) {
if(command[i] == '(') {
continue;
}
if(command[i] >= '2' && command[i] <= '9') {
repeat_command.push(std :: make_pair((command[i] - '0') - 1, i + 1));
continue;
}
if(command[i] == ')') {
auto & stack_top = repeat_command.top();
if(stack_top.first) {
i = stack_top.second;
stack_top.first -= 1;
} else {
repeat_command.pop();
}
} else {
move_robot(robot_loc, command[i]);
}
}
}