#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;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKY2xhc3MgTWF6ZSAvLzEgaXMgd2FsbCwgMCBpcyBwYXNzYWdlCnsKcHVibGljOgogICAgY2xhc3MgRGlyZWN0aW9uCiAgICB7CiAgICBwdWJsaWM6CiAgICAgICAgaW50IHg7CiAgICAgICAgaW50IHk7CiAgICB9OwogICAgY2xhc3MgUGF0aAogICAgewogICAgcHVibGljOgogICAgICAgIHN0ZDo6dmVjdG9yPERpcmVjdGlvbj4gcGF0aDsKICAgICAgICBQYXRoKGNvbnN0IHN0ZDo6c3RyaW5nJiBzKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGF1dG8gYyA6IHMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKGMgPT0gJ1InKSBwYXRoLnB1c2hfYmFjayh7MSwgMH0pOwogICAgICAgICAgICAgICAgZWxzZSBpZihjID09ICdMJykgcGF0aC5wdXNoX2JhY2soeyAtMSwgMH0pOwogICAgICAgICAgICAgICAgZWxzZSBpZihjID09ICdVJykgcGF0aC5wdXNoX2JhY2soezAsIC0xfSk7CiAgICAgICAgICAgICAgICBlbHNlIGlmKGMgPT0gJ0QnKSBwYXRoLnB1c2hfYmFjayh7MCwgMX0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfTsKICAgIGludCBjZWxsc1s0XVs0XTsKICAgIHN0YXRpYyBQYXRoIHRlc3RQYXRoMTsKICAgIHN0YXRpYyBQYXRoIHRlc3RQYXRoMjsKICAgIE1hemUoaW50IGlkKSAvL2NvcGllZCBmcm9tIFZpbmNlbnQgdmFuIGRlciBXZWVsZSdzIGNvZGUKICAgIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDQgKiA0IC0gMjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHggPSAoaSArIDEpICUgNDsKICAgICAgICAgICAgaW50IHkgPSAoaSArIDEpIC8gNDsKICAgICAgICAgICAgY2VsbHNbeF1beV0gPSAoaWQgJiAoMSA8PCBpKSkgPT0gMCA/IDAgOiAxOwogICAgICAgIH0KICAgICAgICBjZWxsc1swXVswXSA9IDA7CiAgICAgICAgY2VsbHNbNCAtIDFdWzQgLSAxXSA9IDA7CiAgICB9CiAgICBib29sIGlzVmFsaWQoY29uc3QgUGF0aCYgcCkgY29uc3QKICAgIHsKICAgICAgICBpZihjZWxsc1swXVswXSkgcmV0dXJuIGZhbHNlOwogICAgICAgIGludCBwb3NYID0gMDsKICAgICAgICBpbnQgcG9zWSA9IDA7CiAgICAgICAgZm9yKGF1dG8mIGQgOiBwLnBhdGgpCiAgICAgICAgewogICAgICAgICAgICBpbnQgbW92ZVggPSBkLng7CiAgICAgICAgICAgIGludCBtb3ZlWSA9IGQueTsKICAgICAgICAgICAgaW50IGFmdGVyTW92ZVggPSBwb3NYICsgbW92ZVg7CiAgICAgICAgICAgIGludCBhZnRlck1vdmVZID0gcG9zWSArIG1vdmVZOwogICAgICAgICAgICBpZihhZnRlck1vdmVYIDwgMCB8fCBhZnRlck1vdmVYID4gMyB8fCBhZnRlck1vdmVZIDwgMCB8fCBhZnRlck1vdmVZID4gMykgY29udGludWU7CiAgICAgICAgICAgIGlmKGNlbGxzW2FmdGVyTW92ZVhdW2FmdGVyTW92ZVldKSBjb250aW51ZTsKICAgICAgICAgICAgcG9zWCA9IGFmdGVyTW92ZVg7CiAgICAgICAgICAgIHBvc1kgPSBhZnRlck1vdmVZOwogICAgICAgICAgICBpZihwb3NYID09IDMgJiYgcG9zWSA9PSAzKSByZXR1cm4gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIChwb3NYID09IDMgJiYgcG9zWSA9PSAzKTsKICAgIH0KCiAgICBzdGF0aWMgc3RkOjp2ZWN0b3I8TWF6ZT4gZ2VuZXJhdGVNYXplcygpIC8vY29waWVkIGZyb20gVmluY2VudCB2YW4gZGVyIFdlZWxlJ3MgY29kZQogICAgewogICAgICAgIHN0ZDo6dmVjdG9yPE1hemU+IG1hemVzOwogICAgICAgIG1hemVzLnJlc2VydmUoNTEwMCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxNjM4NDsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgTWF6ZSBtYXplKGkpOwogICAgICAgICAgICBpZiAoIW1hemUuaXNWYWxpZChNYXplOjp0ZXN0UGF0aDEpICYmIG1hemUuaXNWYWxpZChNYXplOjp0ZXN0UGF0aDIpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBtYXplcy5wdXNoX2JhY2sobWF6ZSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIG1hemVzOwogICAgfQogICAgc3RhdGljIHN0ZDo6c3RyaW5nIHRyeU1pbmltaXplUGF0aChzdGQ6OnN0cmluZyBzKQogICAgewogICAgICAgIGludCBzaXplID0gcy5zaXplKCk7CgogICAgICAgIGZvcihpbnQgaSA9IDA7IGk8c2l6ZTsrK2kpCiAgICAgICAgewogICAgICAgICAgICBzdGQ6OnN0cmluZyBzcyA9IHM7CiAgICAgICAgICAgIHNzLmVyYXNlKGksMSk7CiAgICAgICAgICAgIHRlc3RQYXRoMSA9IFBhdGgoc3MpOyAvL3dlIHJlcGxhY2UgdGVzdFBhdGgxIHNvIHRoYXQgZ2VuZXJhdGVNYXplIGZ1bmN0aW9uIHdpbGwgdXNlIGl0CiAgICAgICAgICAgIHN0ZDo6Y291dCA8PCBzcy5zdWJzdHIoMCwgaSkgPDwgJyAnIDw8IHNzLnN1YnN0cihpKTsKICAgICAgICAgICAgaWYoZ2VuZXJhdGVNYXplcygpLnNpemUoKSA9PSAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzdGQ6OmNvdXQgPDwgIiByZW1vdmVkICIgPDwgc1tpXSA8PCAiIGF0ICIgPDwgaTsKICAgICAgICAgICAgICAgIHMuZXJhc2UoaSwxKTsKICAgICAgICAgICAgICAgIC0tc2l6ZTsKICAgICAgICAgICAgICAgIC0taTsKICAgICAgICAgICAgfQogICAgICAgICAgICBzdGQ6OmNvdXQgPDwgJ1xuJzsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHM7CiAgICB9Cn07Ck1hemU6OlBhdGggTWF6ZTo6dGVzdFBhdGgxID0gTWF6ZTo6UGF0aCgiUlJEUlJSRFJMRFJEUkxETFVVTFVSVVVVTFVMTEREUkRERFJEVVJEUkQiKTsgLy90aG9zZSB0d28gbXVzdCBhbnkgY2hlY2tlZCBhbmQgd29ya2luZyBwYXRocwpNYXplOjpQYXRoIE1hemU6OnRlc3RQYXRoMiA9IE1hemU6OlBhdGgoIlJSRFJSUkRSTERSRFJMRExVVUxVUlVVVUxVTExERFJERERSRFVSRFJEIik7CmludCBtYWluKCkKewogICAgc3RkOjpjb3V0IDw8ICJcbk1pbmltaXplZDogIiA8PCBNYXplOjp0cnlNaW5pbWl6ZVBhdGgoIlJSRFJSUkRSTERSRFJMRExVVUxVUlVVVUxVTExERFJERERSRFVSRFJEIik7CiAgICByZXR1cm4gMDsKfQo=