【連結の判定】FINAL問題 連結の判定 (paizaランク A 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】FINAL問題 連結の判定 (paizaランク A 相当)
※リンク先へ移動する為には「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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $m = $input[1]; for($i = 1;$i <= $n;$i++){ //マップの作成 for($j = 1;$j <= $n;$j++){ if($i == $j){ $array[$i][$j] = 1; } else { $array[$i][$j] = 0; } } } $queue = array(); //探索地点を格納する配列 for($i = 0;$i < $m;$i++){ $test = explode(" ",trim(fgets(STDIN))); $a = $test[0]; $b = $test[1]; if($i == 0){ $queue[] = $a; //幅優先探索の始点を「$queue」に格納する } $array[$a][$b] = 1; //辺で結ばれている地点に1を入れる $array[$b][$a] = 1; //辺で結ばれている地点に1を入れる } while(!empty($queue)){ //空になるまで以下の処理を続ける（幅優先探索を行う） $now = array_shift($queue); //「$now」に「$queue」の先頭の値を取り出し、「$queue」から削除する for($i = 1;$i <= $n;$i++){ if($now != $i){ if($array[$now][$i] == 1){ //「$i」が探索地点と結ばれている「$now」と結ばれているのならば… for($j = 1;$j <= $n;$j++){ if($array[$i][$j] == 1 && $array[$now][$j] == 0){ //「$i」と結ばれている「$j」地点があり、かつ「$now」と「$j」のマッピングが完了していない時 $array[$now][$j] = 1; //マッピングする $array[$j][$now] = 1; //マッピングする array_push($queue,$j); //「$queue」に「$j」を格納する } } } } } } //print_r($array); $counter = 0; //結ばれていない箇所がないかのカウンター foreach($array as $value1){ foreach($value1 as $value2){ if($value2 == 0){ //結ばれていないことを示す「0」があった場合 $counter++; //カウンターの値を1増やす } } } if($counter > 0){ //カウンターの値が0以上なら echo "NO"; //連結していない } else { echo "YES"; //連結している } ?> |
