#include <iostream>
#include <vector>

class Maze //1 is wall, 0 is passage
{
public:
    class Direction
    {
    public:
        int x;
        int y;
    };
    class Path
    {
    public:
        std::vector<Direction> path;
        Path(const std::string& s)
        {
            for(auto c : s)
            {
                if(c == 'R') path.push_back({1, 0});
                else if(c == 'L') path.push_back({ -1, 0});
                else if(c == 'U') path.push_back({0, -1});
                else if(c == 'D') path.push_back({0, 1});
            }
        }
    };
    int cells[4][4];
    static Path testPath1;
    static Path testPath2;
    Maze(int id) //copied from Vincent van der Weele's code
    {
        for (int i = 0; i < 4 * 4 - 2; i++)
        {
            int x = (i + 1) % 4;
            int y = (i + 1) / 4;
            cells[x][y] = (id & (1 << i)) == 0 ? 0 : 1;
        }
        cells[0][0] = 0;
        cells[4 - 1][4 - 1] = 0;
    }
    bool isValid(const Path& p) const
    {
        if(cells[0][0]) return false;
        int posX = 0;
        int posY = 0;
        for(auto& d : p.path)
        {
            int moveX = d.x;
            int moveY = d.y;
            int afterMoveX = posX + moveX;
            int afterMoveY = posY + moveY;
            if(afterMoveX < 0 || afterMoveX > 3 || afterMoveY < 0 || afterMoveY > 3) continue;
            if(cells[afterMoveX][afterMoveY]) continue;
            posX = afterMoveX;
            posY = afterMoveY;
            if(posX == 3 && posY == 3) return true;
        }
        return (posX == 3 && posY == 3);
    }

    static std::vector<Maze> generateMazes() //copied from Vincent van der Weele's code
    {
        std::vector<Maze> mazes;
        mazes.reserve(5100);
        for (int i = 0; i < 16384; ++i)
        {
            Maze maze(i);
            if (!maze.isValid(Maze::testPath1) && maze.isValid(Maze::testPath2))
            {
                mazes.push_back(maze);
            }
        }
        return mazes;
    }
    static std::string tryMinimizePath(std::string s)
    {
        int size = s.size();

        for(int i = 0; i<size;++i)
        {
            std::string ss = s;
            ss.erase(i,1);
            testPath1 = Path(ss); //we replace testPath1 so that generateMaze function will use it
            std::cout << ss.substr(0, i) << ' ' << ss.substr(i);
            if(generateMazes().size() == 0)
            {
                std::cout << " removed " << s[i] << " at " << i;
                s.erase(i,1);
                --size;
                --i;
            }
            std::cout << '\n';
        }
        return s;
    }
};
Maze::Path Maze::testPath1 = Maze::Path("RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD"); //those two must any checked and working paths
Maze::Path Maze::testPath2 = Maze::Path("RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD");
int main()
{
    std::cout << "\nMinimized: " << Maze::tryMinimizePath("RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD");
    return 0;
}