想自己做网站怎么做,重庆市工程造价信息价查询,如何自主建设企业网站,黑龙江省公共资源题目#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;
}
