Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?
- // Why do we need the nodes?
- //$nodes = json_decode('[{"x":3,"y":6,"id":0},{"x":1,"y":1,"id":1},{"x":3,"y":1,"id":2},{"x":3,"y":4,"id":3},{"x":5,"y":1,"id":4},{"x":6,"y":1,"id":5},{"x":4,"y":3,"id":6},{"x":1,"y":6,"id":7},{"x":4,"y":6,"id":8},{"x":6,"y":6,"id":9},{"x":3,"y":9,"id":10},{"x":6,"y":11,"id":11}]');
- $paths = json_decode('[[0,1],[0,2],[0,3],[3,2],[3,6],[6,4],[6,5],[3,9],[9,9],[9,10],[10,0],[10,11],[11,10],[10,8],[8,3],[3,1]]');
- // Convert paths to a hash: from -> [to]
- $newPaths = array();
- foreach($paths as $path) {
- if (!$newPaths[$path[0]]) $newPaths[$path[0]] = array();
- array_push($newPaths[$path[0]], $path[1]);
- }
- $paths = $newPaths;
- // Use a Depth First Search, where:
- // $paths is the original $paths array
- // $visited are the nodes that we already visited (in order to avoid loops)
- // $from is the node where we are parting from
- // $to is the node where we want to arrive
- // $result is the result that will finally be returned
- function findPath(&$paths, &$visited, $from, $to, &$result) {
- $next = $paths[$from];
- if (!$next) return false;
- foreach($next as $node) {
- if ($node == $to) {
- array_push($result, $from);
- array_push($result, $to);
- return $result;
- }
- if ($visited[$node]) continue;
- $visited[$node] = true;
- array_push($result, $from);
- if (findPath($paths, $visited, $node, $to, $result)) {
- return $result;
- }
- array_pop($result);
- unset($visited[$node]);
- }
- }
- $result = array();
- $visited = array();
- findPath($paths, $visited, '0', '11', $result);
- print_r($result);
- ?>
Add Comment
Please, Sign In to add comment