algorithm/maze_short_path_depth.php at master · 582302894/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
<?php

$maze = [
    [0, 0, 2, 0],
    [0, 0, 0, 0],
    [0, 0, 2, 0],
    [0, 2, 9, 0],
    [0, 0, 0, 2],
];
//顺时针 右、下、左、上
$next = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
];
$book;
$min = 9999;

class Path {
    public $top = 0;
    public $data = null;

    public function in($data) {
        $this->data[$this->top] = ($data[0] + 1) . ',' . ($data[1] + 1);
        $this->top++;
    }
    public function out() {
        $this->top--;
    }
    public function show() {
        for ($i = 0; $i < $this->top; $i++) {
            echo $this->data[$i] . "\t";
        }
        echo "\n";
    }
}
$path = new Path();

function dfs($x, $y, $step) {
    global $book, $min, $next, $maze, $path;
    if ($maze[$x][$y] == 9) {
        $path->show();
        if ($step < $min) {
            $min = $step;
        }
        return;
    }
    for ($i = 0; $i < 4; $i++) {
        $nextX = $x + $next[$i][0];
        $nextY = $y + $next[$i][1];
        if ($nextX > 4 || $nextX < 0 || $nextY > 3 || $nextY < 0) {
            continue;
        }
        if (
            (
                $maze[$nextX][$nextY] == 0
                ||
                $maze[$nextX][$nextY] == 9
            )
            &&
            (
                !isset($book[$nextX][$nextY])
                ||
                $book[$nextX][$nextY] == 0
            )
        ) {
            $path->in([$nextX, $nextY]);
            $book[$nextX][$nextY] = 1;
            dfs($nextX, $nextY, $step + 1);
            $path->out();
            $book[$nextX][$nextY] = 0;
        }
    }
}

function main() {
    global $book, $path;
    $book[0][0] = 1;
    $path->in([0, 0]);
    dfs(0, 0, 0);
}

main();
echo $min;