Submission #163177

---

Source Code Expand

<?php
$DEBUG = 0;
//$DEBUG = 1;

if ($DEBUG)
{
    ini_set('display_errors', 'On');
    ini_set('error_reporting', E_ALL & ~E_NOTICE);
    $time_s = microtime(TRUE);
}

# 読み込み
fscanf(STDIN, "%d %d", $sizeX, $sizeY);
fscanf(STDIN, "%d %d", $startX, $startY);
fscanf(STDIN, "%d %d", $goalX, $goalY);

$arrMaze = array();

for ($i = 0; $i < $sizeX; $i++)
{
    for ($j = 0; $j < $sizeY; $j++)
    {
        $arrMaze[$i][$j] = "";
    }
}
// ステップ数
//$arrMazeStep = $arrMaze;
$arrMazeStep = array();

for ($i = 0; $i < $sizeY; $i++)
{
    fscanf(STDIN, "%s", $tmp);
    for ($j = 0; $j < strlen($tmp); $j++)
    {
        $arrMaze[$i][$j] = substr($tmp, $j, 1);
    }
}

//if ($DEBUG) dumpX($arrMaze);
//if ($DEBUG) dumpX($arrMazeStep);

$currX = $startX - 1;
$currY = $startY - 1;

$arrMazeStep[$currX][$currY] = 0;

$arrMove = array(
                array("dx" => "-1", "dy" => "0"),
                array("dx" => "1", "dy" => "0"),
                array("dx" => "0", "dy" => "-1"),
                array("dx" => "0", "dy" => "1"),
);

$q = array();

$tmpArray = array();
$tmpArray['x'] = $currX;
$tmpArray['y'] = $currY;
$tmpArray['s'] = 0;
$arrMazeStep[$currX][$currY] = 0;

array_unshift($q, $tmpArray);
if ($DEBUG) var_dump($q);

while(TRUE)
{
    $arr = array_shift($q);
    $arrMazeStep[$arr['x']][$arr['y']] = $arr['s'];
    //dumpX($arrMazeStep);
    
    foreach ($arrMove as $v)
    {
        //echo "Z";
        $tmpArray = array();
        $tmpArray['x'] = $arr['x'] + $v['dx'];
        $tmpArray['y'] = $arr['y'] + $v['dy'];
        $tmpArray['s'] = $arr['s'] + 1;
        if ($arrMaze[$tmpArray['x']][$tmpArray['y']] == '.')
        {
            //echo "A";
            if (!isset($arrMazeStep[$tmpArray['x']][$tmpArray['y']]))
            {
                if ($DEBUG) echo "A";
                $q[] = $tmpArray;
                $arrMazeStep[$tmpArray['x']][$tmpArray['y']] = $tmpArray['s'];
            } elseif ($arrMazeStep[$tmpArray['x']][$tmpArray['y']] > $tmpArray['s'])
            {
                if ($DEBUG) echo "B";
                $q[] = $tmpArray;
            } else
            {
                //echo "X";
            }
        }
    }
    //var_dump($q);
    //echo count($q) . PHP_EOL;
    if (count($q) == 0) break;
}
if ($DEBUG) echo "answer is ... ";
echo $arrMazeStep[$goalX-1][$goalY-1].PHP_EOL;
if ($DEBUG) echo "FINISH\n";

function dumpX($arr)
{
    global $sizeX;
    global $sizeY;
    
    echo "\n";
    for ($i = 0; $i < $sizeX; $i++)
    {
        for ($j = 0; $j < $sizeY; $j++)
        {
            printf("%02d ", $arr[$i][$j]);
        }
        echo "\n";
    }
    echo "\n";
}

if ($DEBUG)
{
    $time_f = microtime(TRUE);
    printf("time = %1.3f sec \n", $time_f - $time_s);
}

Submission Info

Judge Result