fork download
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. class Maze //1 is wall, 0 is passage
  5. {
  6. public:
  7. class Direction
  8. {
  9. public:
  10. int x;
  11. int y;
  12. };
  13. class Path
  14. {
  15. public:
  16. std::vector<Direction> path;
  17. Path(const std::string& s)
  18. {
  19. for(auto c : s)
  20. {
  21. if(c == 'R') path.push_back({1, 0});
  22. else if(c == 'L') path.push_back({ -1, 0});
  23. else if(c == 'U') path.push_back({0, -1});
  24. else if(c == 'D') path.push_back({0, 1});
  25. }
  26. }
  27. };
  28. int cells[4][4];
  29. static Path testPath1;
  30. static Path testPath2;
  31. Maze(int id) //copied from Vincent van der Weele's code
  32. {
  33. for (int i = 0; i < 4 * 4 - 2; i++)
  34. {
  35. int x = (i + 1) % 4;
  36. int y = (i + 1) / 4;
  37. cells[x][y] = (id & (1 << i)) == 0 ? 0 : 1;
  38. }
  39. cells[0][0] = 0;
  40. cells[4 - 1][4 - 1] = 0;
  41. }
  42. bool isValid(const Path& p) const
  43. {
  44. if(cells[0][0]) return false;
  45. int posX = 0;
  46. int posY = 0;
  47. for(auto& d : p.path)
  48. {
  49. int moveX = d.x;
  50. int moveY = d.y;
  51. int afterMoveX = posX + moveX;
  52. int afterMoveY = posY + moveY;
  53. if(afterMoveX < 0 || afterMoveX > 3 || afterMoveY < 0 || afterMoveY > 3) continue;
  54. if(cells[afterMoveX][afterMoveY]) continue;
  55. posX = afterMoveX;
  56. posY = afterMoveY;
  57. if(posX == 3 && posY == 3) return true;
  58. }
  59. return (posX == 3 && posY == 3);
  60. }
  61.  
  62. static std::vector<Maze> generateMazes() //copied from Vincent van der Weele's code
  63. {
  64. std::vector<Maze> mazes;
  65. mazes.reserve(5100);
  66. for (int i = 0; i < 16384; ++i)
  67. {
  68. Maze maze(i);
  69. if (!maze.isValid(Maze::testPath1) && maze.isValid(Maze::testPath2))
  70. {
  71. mazes.push_back(maze);
  72. }
  73. }
  74. return mazes;
  75. }
  76. static std::string tryMinimizePath(std::string s)
  77. {
  78. int size = s.size();
  79.  
  80. for(int i = 0; i<size;++i)
  81. {
  82. std::string ss = s;
  83. ss.erase(i,1);
  84. testPath1 = Path(ss); //we replace testPath1 so that generateMaze function will use it
  85. std::cout << ss.substr(0, i) << ' ' << ss.substr(i);
  86. if(generateMazes().size() == 0)
  87. {
  88. std::cout << " removed " << s[i] << " at " << i;
  89. s.erase(i,1);
  90. --size;
  91. --i;
  92. }
  93. std::cout << '\n';
  94. }
  95. return s;
  96. }
  97. };
  98. Maze::Path Maze::testPath1 = Maze::Path("RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD"); //those two must any checked and working paths
  99. Maze::Path Maze::testPath2 = Maze::Path("RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD");
  100. int main()
  101. {
  102. std::cout << "\nMinimized: " << Maze::tryMinimizePath("RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD");
  103. return 0;
  104. }
  105.  
Success #stdin #stdout 0.26s 3796KB
stdin
Standard input is empty
stdout
 RDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD
R DRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD
RR RRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD
RRD RRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD removed R at 3
RRD RDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD
RRDR DRLDRDRLDLUULURUUULULLDDRDDDRDURDRD
RRDRR RLDRDRLDLUULURUUULULLDDRDDDRDURDRD
RRDRRD LDRDRLDLUULURUUULULLDDRDDDRDURDRD
RRDRRDR DRDRLDLUULURUUULULLDDRDDDRDURDRD
RRDRRDRL RDRLDLUULURUUULULLDDRDDDRDURDRD
RRDRRDRLD DRLDLUULURUUULULLDDRDDDRDURDRD
RRDRRDRLDR RLDLUULURUUULULLDDRDDDRDURDRD
RRDRRDRLDRD LDLUULURUUULULLDDRDDDRDURDRD
RRDRRDRLDRDR DLUULURUUULULLDDRDDDRDURDRD
RRDRRDRLDRDRL LUULURUUULULLDDRDDDRDURDRD
RRDRRDRLDRDRLD UULURUUULULLDDRDDDRDURDRD
RRDRRDRLDRDRLDL ULURUUULULLDDRDDDRDURDRD
RRDRRDRLDRDRLDLU LURUUULULLDDRDDDRDURDRD
RRDRRDRLDRDRLDLUU URUUULULLDDRDDDRDURDRD
RRDRRDRLDRDRLDLUUL RUUULULLDDRDDDRDURDRD removed U at 18
RRDRRDRLDRDRLDLUUL UUULULLDDRDDDRDURDRD
RRDRRDRLDRDRLDLUULR UULULLDDRDDDRDURDRD removed U at 19
RRDRRDRLDRDRLDLUULR ULULLDDRDDDRDURDRD removed U at 19
RRDRRDRLDRDRLDLUULR LULLDDRDDDRDURDRD
RRDRRDRLDRDRLDLUULRU ULLDDRDDDRDURDRD
RRDRRDRLDRDRLDLUULRUL LLDDRDDDRDURDRD
RRDRRDRLDRDRLDLUULRULU LDDRDDDRDURDRD
RRDRRDRLDRDRLDLUULRULUL DDRDDDRDURDRD
RRDRRDRLDRDRLDLUULRULULL DRDDDRDURDRD
RRDRRDRLDRDRLDLUULRULULLD RDDDRDURDRD
RRDRRDRLDRDRLDLUULRULULLDD DDDRDURDRD
RRDRRDRLDRDRLDLUULRULULLDDR DDRDURDRD
RRDRRDRLDRDRLDLUULRULULLDDRD DRDURDRD
RRDRRDRLDRDRLDLUULRULULLDDRDD RDURDRD
RRDRRDRLDRDRLDLUULRULULLDDRDDD DURDRD
RRDRRDRLDRDRLDLUULRULULLDDRDDDR URDRD
RRDRRDRLDRDRLDLUULRULULLDDRDDDRD RDRD
RRDRRDRLDRDRLDLUULRULULLDDRDDDRDU DRD
RRDRRDRLDRDRLDLUULRULULLDDRDDDRDUR RD
RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURD D
RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDR 

Minimized: RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD