46、PHP实现矩阵中的路径

题目： PHP实现矩阵中的路径

描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如:
a b c e
s f c s
a d e e
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

<?php

function hasPath($matrix, $rows, $cols, $path)
{
    // write code here
    $m = str_split($matrix,$cols);
    $visited = [];
    for($i=0; $i<$rows; $i++){
        for($j=0; $j<$cols; $j++){
            if(back($m,$rows,$cols,$i,$j,$path,$visited)){
                return true;
            }
        }
    }
    return false;
}
 
function back(&$m,&$rows,&$cols,$i,$j,$path,&$v)
{
    if($i<0 || $j<0|| $cols<=$j || $rows<=$i || $v[$i][$j]==1){
        return false;
    }
    $v[$i][$j] = 1;
    if(substr($path,0,1)==$m[$i][$j]){
        if(strlen($path)==1){
            return true;
        }
          if(back($m,$rows,$cols,$i+1,$j,substr($path,1),$v)||
             back($m,$rows,$cols,$i-1,$j,substr($path,1),$v)||
             back($m,$rows,$cols,$i,$j+1,substr($path,1),$v)||
             back($m,$rows,$cols,$i,$j-1,substr($path,1),$v)){
             return true;
            }
    }
    $v[$i][$j] = 0;
    return false;
}
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