SO业务编排>> maze-solver>> 返回
项目作者： maxim-andrews

项目描述 ：
Simple decision tree solver
高级语言： JavaScript
项目地址: git://github.com/maxim-andrews/maze-solver.git
创建时间： 2017-02-01T23:28:52Z
项目社区：https://github.com/maxim-andrews/maze-solver
开源协议：MIT License
下载


Decision tree implementation Build Status

Maze Solver

The problem is very simple: you need to find the way out of the maze.

Maze is given as a rectangular matrix of 0 and 1 characters.

  1. 1110001
  2. 0010001
  3. 1111111
  4. 0000101
  5. 1111101

Maze string should contain width and height of the maze in first line.
The maze itself will follow, with 1 depicting passages and 0 for impassable
walls. You have to provide to maze solver Entry and Exit points and it will find
the shortest path for you. See code below for configuration example:

  1. {
  2.   maze: '31 29
  3. 1111101011101111101110111011111
  4. 1010001010000000100010001010100
  5. 1011111111111110101010111110111
  6. 1000000000100010101010100010100
  7. 1010111110101110111110111010111
  8. 1010001000100000001000000010100
  9. 1111101111111110101110111110111
  10. 0000001000000010101000101010000
  11. 1111101011101111101111101010111
  12. 1000101010000010000000100000101
  13. 1011101110111110101111101110101
  14. 1000000010100000101000001010001
  15. 1011111010111111111111101011111
  16. 1000100000100000000000101010101
  17. 1111111011101011101110101010101
  18. 0010000000101000100010000000100
  19. 1111111110101111111111111111101
  20. 1010000000101010100010000000001
  21. 1011101111111010101110111111111
  22. 1000101000100000101000000000100
  23. 1011111110111110101011101111111
  24. 1010001000000010001000101010001
  25. 1010111110101110111110111010101
  26. 1000001010100010000010001010100
  27. 1110111011101111101110101011111
  28. 1000101000100000001000101000101
  29. 1110101011111111101110111110101
  30. 1000101000001000001000001000101
  31. 1110101011111110111111111011101',
  32.   start: [
  33.     { x: 30, y:  0, label: 'A' },
  34.     { x: 30, y: 28, label: 'B' },
  35.     { x:  0, y: 28, label: 'C' }
  36.   ],
  37.   end: [ { x: 0, y: 0, label: 'X' } ]
  38. }

Result will show how many steps and in which direction from the given point you have to make
to reach the goal. Where U denotes step up, L is one step left, R and D are steps right and down respectively.
The result will be produced in compact way where number denotes the number of steps in the current direction, like this:

  1. [ '4L6D4L4D4L2D8L2U4R4U4L4U8L2U2L',
  2.   '4U4L4U2L8D6L4U2R2U2L4U2R2U8L2D2L8U4R4U4L4U8L2U2L',
  3.   '12U2R2D2R2D2R2U4R8U4R4U4L4U8L2U2L' ]

The result is an array sorted by the starting point label name.