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