結果

問題 No.3 ビットすごろく
ユーザー papinianuspapinianus
提出日時 2016-07-29 12:32:59
言語 PHP
(8.3.4)
結果
AC  
実行時間 22 ms / 5,000 ms
コード長 1,274 bytes
コンパイル時間 1,108 ms
コンパイル使用メモリ 18,676 KB
実行使用メモリ 18,948 KB
最終ジャッジ日時 2023-09-14 00:04:14
合計ジャッジ時間 3,047 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
18,848 KB
testcase_01 AC 16 ms
18,892 KB
testcase_02 AC 15 ms
18,820 KB
testcase_03 AC 16 ms
18,928 KB
testcase_04 AC 16 ms
18,948 KB
testcase_05 AC 18 ms
18,936 KB
testcase_06 AC 17 ms
18,812 KB
testcase_07 AC 16 ms
18,812 KB
testcase_08 AC 17 ms
18,840 KB
testcase_09 AC 19 ms
18,844 KB
testcase_10 AC 20 ms
18,916 KB
testcase_11 AC 19 ms
18,780 KB
testcase_12 AC 18 ms
18,732 KB
testcase_13 AC 16 ms
18,860 KB
testcase_14 AC 20 ms
18,940 KB
testcase_15 AC 20 ms
18,920 KB
testcase_16 AC 20 ms
18,948 KB
testcase_17 AC 20 ms
18,784 KB
testcase_18 AC 16 ms
18,824 KB
testcase_19 AC 21 ms
18,848 KB
testcase_20 AC 16 ms
18,612 KB
testcase_21 AC 17 ms
18,912 KB
testcase_22 AC 20 ms
18,852 KB
testcase_23 AC 21 ms
18,932 KB
testcase_24 AC 21 ms
18,836 KB
testcase_25 AC 22 ms
18,812 KB
testcase_26 AC 16 ms
18,920 KB
testcase_27 AC 17 ms
18,836 KB
testcase_28 AC 20 ms
18,896 KB
testcase_29 AC 19 ms
18,768 KB
testcase_30 AC 17 ms
18,816 KB
testcase_31 AC 16 ms
18,880 KB
testcase_32 AC 19 ms
18,836 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php
$num = trim(fgets(STDIN));
$step = [0=>0,1=>1,2=>2,3=>3,5=>4]; //pos=>step //array_fillで-1？
$queue = [[5,3]]; //[pos,src]
$hist = [];
while(count($queue) > 0) {
    $cur = array_shift($queue);
    $curPlace = $cur[0]; //今いる位置
    $curStep = $step[$cur[1]]+1; //今いる位置に至るステップ=元いた位置+1
    $width = substr_count(decbin($curPlace), "1"); //今いる位置から進める距離
    $forward = $curPlace+$width; //前方の移動可能な位置
    $backward = $curPlace-$width; // 公報の移動可能な位置
    if($forward <= $num) { // 前方が移動可能圏内
        if(!isset($step[$forward]) ) { // 到達した事のある位置
            $step[$forward] = $curStep+1; //次の位置への到達ステップを記録、このロジックだと最初に到達したときが最短になるはず
            array_push($queue, [$forward, $curPlace]);
        }
    }
    if($backward > 0) { // 後方が移動可能圏内
        if(!isset($step[$backward]) ) {
            $step[$backward] = $curStep+1; //次の位置への到達ステップを記録
            array_push($queue, [$backward, $curPlace]);
        }
    }
}
if(isset($step[$num])) {
    echo $step[$num];
} else {
    echo -1;
}
echo PHP_EOL;
0