AIO 2021 Q1: Robot Vacuum - Late Night Code

Contest Source: AIO 2021

For this problem, let’s assume the robot starts at \((0,0)\) (the starting point does not matter). Then we can simulate how the robot moves and find out it’s final resting point. We can then use the manhattan distance between the start and the finish in order to determine the shortest distance for the robot to reach the start again. The complexity is \(O(K)\)

C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main () {
    freopen("robotin.txt", "r", stdin);
    freopen("robotout.txt", "w", stdout);

    int K;
    cin >> K;
    string s;
    cin >> s;

    // initialise starting position
    int x = 0;
    int y = 0;

    // simulate robot movement
    for (int i = 0; i < K; i++) {
        if (s[i] == 'N') y++;
        if (s[i] == 'S') y--;
        if (s[i] == 'E') x++;
        if (s[i] == 'W') x--;
    }

    // find the manhattan distance back to the start
    int dist = abs(y-0) + abs(x-0);
    printf("%d\n", dist);
}