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));
|