Solution for "Exploring The Maze

#include "assert.h"
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <time.h>
#include <vector>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b ; ++i)

#define endl '\n'
template<typename T> struct argument_type;
template<typename T, typename U> struct argument_type<T(U)> { typedef U type; };
#define next(t, i) argument_type<void(t)>::type i; cin >> i;

void skip_intro() {
    next(int, n);
    next(int, m);
}

void out(string s) {
    cout << s << endl;
    fflush(stdin);
}

bool inp() {
    next(string, buf);
    if (buf == "EXIT") {
        exit(0);
    }
    return buf == "OK";
}

vector<int> dx = { -1 , 0 , 0 , 1 };
vector<int> dy = { 0 , 1 , -1 , 0 };

bool move_forward(int dir) {
    switch(dir) {
        case 0: out("MOVE LEFT"); break;
        case 1: out("MOVE UP"); break;
        case 2: out("MOVE DOWN"); break;
        case 3: out("MOVE RIGHT"); break;
    }
    return inp();
}

void move_back() {
    out("BACK");
    assert(inp());
}

struct pos {
    int dx, dy, c1;
};

bool operator < (const pos &p1 , const pos &p2) {
    if (p1.dx != p2.dx) return p1.dx < p2.dx;
    if (p1.dy != p2.dy) return p1.dy < p2.dy;
    if (p1.c1 != p2.c1) return p1.c1 < p2.c1;
    return false;
}

set<pos> visited_positions;

// after first 3 moves DSF all (x,y,distance % 4) combinations
void dfs2(pos cur_pos) {
    if (visited_positions.count(cur_pos)) return;

    visited_positions.insert(cur_pos);

    FOR (dir, 0, 4) {
        {
            auto next_pos = cur_pos;
            next_pos.dx += dx[dir];
            next_pos.dy += dy[dir];
            next_pos.c1++;
            next_pos.c1 &= 3;

            if (!visited_positions.count(next_pos) && move_forward(dir)) {
                dfs2(next_pos);

                move_back();
            }
        }
    }
}

// DFS all combinations of three moves
void dfs1(int moves_to_make) {
    if (moves_to_make == 0) {
        pos cur_pos = { 0 , 0, 0 };

        visited_positions.clear();

        dfs2(cur_pos);
    } else {
        FOR (nextDir, 0, 4) {
            if (!move_forward(nextDir)) continue;

            dfs1(moves_to_make - 1);
            move_back();
        }
    }
}

int main() {
    int n, m;
    skip_intro();

    dfs1(3);
}