想自己做网站怎么做,信用网站标准化建设方案,凯里官网,手机网站图片优化题目#xff1a; PHP实现矩阵中的路径
描述#xff1a; 请设计一个函数#xff0c;用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。 路径可以从矩阵中的任意一个格子开始#xff0c;每一步可以在矩阵中向左#xff0c;向右#xff0c;向上#xff0c;向…题目 PHP实现矩阵中的路径
描述 请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。 路径可以从矩阵中的任意一个格子开始每一步可以在矩阵中向左向右向上向下移动一个格子。 如果一条路径经过了矩阵中的某一个格子则该路径不能再进入该格子。 例如: a b c e s f c s a d e e 矩阵中包含一条字符串bcced的路径但是矩阵中不包含abcb路径 因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后路径不能再次进入该格子。
?phpfunction hasPath($matrix, $rows, $cols, $path)
{// write code here$m str_split($matrix,$cols);$visited [];for($i0; $i$rows; $i){for($j0; $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($i0 || $j0|| $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,$i1,$j,substr($path,1),$v)||back($m,$rows,$cols,$i-1,$j,substr($path,1),$v)||back($m,$rows,$cols,$i,$j1,substr($path,1),$v)||back($m,$rows,$cols,$i,$j-1,substr($path,1),$v)){return true;}}$v[$i][$j] 0;return false;
}
