矩阵路径是这样一个点序列:从给定矩阵中任一数字标记的点出发,每一步可以向左、右、上、下四个方向之一移动一格到达下一个点,依次类推而得到的点序列,一条矩阵路径最少包含两个点,同一个点可以多次出现在一条矩阵路径上。现用点的标记数字组成的序列来表示这样的矩阵路径,例如 1 5 6 7 是矩阵中的一条路径,而 8 5 1 4 就不是。判定输入的序列是否表示了一个合规的矩阵路径,若是,输出 1,若不是,输出 0。input 会给出多组序列,每组中间用 0 做分隔符。

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
function hasPath(array $matrix, array $str)
{
if (empty($matrix) || !isset($matrix[0])) {
return false;
}
if (!isset($matrix[0])) {
if (count($matrix) == 1 && count($str) == 1 && $matrix[0][0] == $str[0]) {
return true;
}
}
for ($i = 0; $i < count($matrix); $i++) {
for ($j = 0; $j < count($matrix[0]); $j++) {
if (dfs($matrix, $i, $j, 0, $str)) {
return true;
}
}
}

return false;
}

function dfs($matrix, $rows, $cols, $start, $str)
{
if ($rows < 0 || $rows >= count($matrix) || $cols < 0 || $cols >= count($matrix[0]) || $start < 0) {
return false;
}

if ($start == count($str)) {
return true;
}
if ($matrix[$rows][$cols] === $str[$start]) {
return dfs($matrix, $rows, $cols + 1, $start + 1, $str) ||
dfs($matrix, $rows, $cols - 1, $start + 1, $str) ||
dfs($matrix, $rows + 1, $cols, $start + 1, $str) ||
dfs($matrix, $rows - 1, $cols, $start + 1, $str);
}
return false;
}

$matrix = [
[1,2,3,4],
[5,6,7,8],
[1,4,2,6],
[3,5,1,7]
];
$str = [1,5,6,4];
$str = [3,7,8,6,7,1];
$str = [2,1,5,8,6];
var_dump(hasPath($matrix, $str));