【連結の判定】STEP: 6 りんご拾い（情報を持ちながらの移動） (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】STEP: 6 りんご拾い（情報を持ちながらの移動） (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
前回の問題が解ければ簡単な問題です。移動順を探し出した後は、移動順に対応するリンゴを足して出力の繰り返しです。
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
<?php $n = trim(fgets(STDIN)); for($i = 0;$i < $n - 1;$i++){ $test = explode(" ",trim(fgets(STDIN))); $a = $test[0]; $b = $test[1]; $array[$b][$a] = 1; //隣接している頂点の表記移動順ではない為、$aと$bを逆にしたものもキーとして保存する $array[$a][$b] = 1; //隣接している頂点の表記移動順ではない為、$aと$bを逆にしたものもキーとして保存する } $num= 1; // 検査対象の配列。始点は常に1なので始めは1をいれる $ans = array($num); //この配列に移動順を記録する for($i = 0;$i < $n - 1;$i++){ //始点1を除いた回数分以下の処理を行う(移動順を探索する) foreach($array as $key1 => $value1){ foreach($value1 as $key2 => $value2){ if($key1 == $num){ //もし「$key1」が「$num」であり… if(in_array($key2 , $ans ,true) == false){ //もし「$key2」が「$ans」の中にないのならば… array_push($ans,$key2); //「$ans」に「$key2」を記録する $num = $key2; //検査対象に$key2を入れる break; } } elseif($key2 == $num){ //もし「$key2」が「$num」であり… if(in_array($key1 , $ans ,true) == false){ //もし「$key1」が「$ans」の中にないのならば… array_push($ans,$key1); //「$ans」に「$key1」を記録する $num = $key1; //検査対象に$key1を入れる break; } } } } } $quantity = array(); //各地点のリンゴの個数を記録する配列作成 for($i = 1;$i <= $n;$i++){ //各地点のリンゴの個数を記録する $quantity[$i] = trim(fgets(STDIN)); } $answer = 0; //各地点のリンゴの合計を記録する配列 for($i = 0;$i < $n;$i++){ //答えを出力する $answer += $quantity[$ans[$i]]; //リンゴを合計していく echo $answer."\n"; } ?> |
