剑指offer(PHP版改写)---矩阵中的路径

àì夳堔傛蜴生んèń 2021-10-26 11:54 215阅读 0赞

<?php
    /**
     * Created by PhpStorm.
     * User: ftx
     * Date: 2019/7/24
     * Time: 11:18 AM
     */
    
    //回溯法 找出矩阵中的路径
    
    /**
     * @param $matrix  矩阵数组
     * @param $rows    行数
     * @param $cols    列数
     * @param $str     要寻找的字符串
     */
    function hasPath($matrix,$rows,$cols,$str){
       
        if ($matrix==null||$rows<1||$cols<1||$str==null){
       
            return false;
        }
    
        $visited = [$rows*$cols];
        for($i = 0;$i<count($visited);++$i){
       
            $visited[$i]=0;
        }
        for ($row = 0;$row<$rows;++$row){
       
            for ($col=0;$col<$cols;++$col){
       
                if (hasPathCore($matrix,$rows,$cols,$row,$col,$str,$visited)){
       
                    return true;
                }
            }
        }
    
        return 0;
    }
    //
    function hasPathCore($matrix,$rows,$cols,$row,$col,$str,$visited)
    {
       
        if (count($str) <= 0) {
       
            return true;
        }
    
        $hasPath = 0;
        $index = $row * $cols + $col;
    //
        if ($row < 0 || $row >= $rows || $col < 0 || $col >= $cols || $matrix[$index] == false || $matrix[$index] != $str[0]) {
       
            return false;
        }
        $visited[$index] = true;
        $strRest = array_slice($str, 1);
        if (hasPathCore($matrix, $rows, $cols,  $row + 1, $col,$strRest, $visited) ||
            hasPathCore($matrix, $rows, $cols,  $row - 1, $col, $strRest,$visited) ||
            hasPathCore($matrix, $rows, $cols, $row, $col + 1,$strRest, $visited) ||
            hasPathCore($matrix, $rows, $cols, $row, $col - 1, $strRest,$visited)) {
       
            $hasPath = 1;
        } else {
       
            $visited[$index] = false;
        }
    
        return $hasPath;
    }
    $matrix = ['A','B','C','E','S','F','C','S','A','D','E','F'];
    $str = ['A','B','C','D'];
    print_r(hasPath($matrix,3,4,$str));

转载于:https://www.cnblogs.com/cyworz/p/11243095.html