どこぞの会社の入社試験をPHPで
http://okajima.air-nifty.com/b/2010/01/post-abc6.htmlこれ。
誰よりもウンコな解き方をしたと思います。
所要時間90分。
というかこれ「解いた」っていいのか微妙。
とりあえず今個人的にアツいPHPで書いておりました。(PHP以外忘れたから説が濃厚です)
ちなみに僕のPHPはほぼ我流なので書き方変だよ!とかかなりありそうでごんす。
「入力データのバリデーション(長方形になっているか、スタート・ゴールが1つずつあるかどうか、等)は不要」
とのことで、
・外がカベで覆われてない場合
・ゴールできない迷路
・長方形じゃないinput
このへんは来ないものとして考えてません、除外
そんなわけでウンコソース。
<pre> <?php //設定 $inputText = "input2.txt"; $outputText = "output2.txt"; class Maze{ const START = 'S'; const GOAL = 'G'; const WALL = '*'; const ROAD = ' '; const WAY = '$'; const WALK_NORTH = 1; const WALK_EAST = 2; const WALK_WEST = 3; const WALK_SOUTH = 4; var $maze = array(); var $mazeClone; var $start = array(); var $goal = array(); public function __construct($inputText){ $inputText = trim($inputText); $rows = explode("\n", $inputText); $rowCount = count($rows); for($i = 0; $i < $rowCount; $i++){ $row = trim($rows[$i]); $cells = array(); $cellCount = strlen($row); for($j = 0; $j < $cellCount; $j++){ $cell = substr($row, $j, 1); $cells[] = $cell; if($cell === self::START){ $this->start[0] = $i; $this->start[1] = $j; } if($cell === self::GOAL){ $this->goal[0] = $i; $this->goal[1] = $j; } } $this->maze[] = $cells; } $this->mazeClone = $this->maze; $this->maze[$this->start[0]][$this->start[1]] = 0; } private function getNextPoint($currentPoint, $mode){ switch($mode){ case self::WALK_NORTH: return array($currentPoint[0] - 1, $currentPoint[1]); case self::WALK_EAST: return array($currentPoint[0], $currentPoint[1] + 1); case self::WALK_WEST: return array($currentPoint[0], $currentPoint[1] - 1); case self::WALK_SOUTH: return array($currentPoint[0] + 1, $currentPoint[1]); } } private function walkTo($point, $distance){ if($this->maze[$point[0]][$point[1]] === self::WALL){ return; } if(is_int($this->maze[$point[0]][$point[1]]) && $this->maze[$point[0]][$point[1]] <= $distance){ return; } $this->maze[$point[0]][$point[1]] = $distance; $this->walkTo($this->getNextPoint($point, self::WALK_NORTH), $distance + 1, $point); $this->walkTo($this->getNextPoint($point, self::WALK_EAST), $distance + 1, $point); $this->walkTo($this->getNextPoint($point, self::WALK_WEST), $distance + 1, $point); $this->walkTo($this->getNextPoint($point, self::WALK_SOUTH), $distance + 1, $point); return; } private function backTo($point, $distance){ if($distance == 0){ return true; } if($this->maze[$point[0]][$point[1]] === self::WALL){ return false; } if($this->maze[$point[0]][$point[1]] == $distance){ $this->mazeClone[$point[0]][$point[1]] = self::WAY; if($this->backTo($this->getNextPoint($point, self::WALK_NORTH), $distance - 1)){ return true; } if($this->backTo($this->getNextPoint($point, self::WALK_EAST), $distance - 1)){ return true; } if($this->backTo($this->getNextPoint($point, self::WALK_WEST), $distance - 1)){ return true; } if($this->backTo($this->getNextPoint($point, self::WALK_SOUTH), $distance - 1)){ return true; } } return false; } public function start(){ $this->walkTo($this->getNextPoint($this->start, self::WALK_NORTH), 1); $this->walkTo($this->getNextPoint($this->start, self::WALK_EAST), 1); $this->walkTo($this->getNextPoint($this->start, self::WALK_WEST), 1); $this->walkTo($this->getNextPoint($this->start, self::WALK_SOUTH), 1); } public function getWay(){ if($this->backTo($this->getNextPoint($this->goal, self::WALK_NORTH), $this->maze[$this->goal[0]][$this->goal[1]] - 1)){ return; } if($this->backTo($this->getNextPoint($this->goal, self::WALK_EAST), $this->maze[$this->goal[0]][$this->goal[1]] - 1)){ return; } if($this->backTo($this->getNextPoint($this->goal, self::WALK_WEST), $this->maze[$this->goal[0]][$this->goal[1]] - 1)){ return; } if($this->backTo($this->getNextPoint($this->goal, self::WALK_SOUTH), $this->maze[$this->goal[0]][$this->goal[1]] - 1)){ return; } } public function output($outputText){ $rows = array(); foreach($this->mazeClone as $row){ $rows[] = implode("", $row); } $out = implode("\n", $rows); file_put_contents($outputText, $out); } } echo '<a href="'.$inputText.'">'.$inputText.'</a>'."\n"; $clsMaze = new Maze(file_get_contents($inputText)); $clsMaze->start(); $clsMaze->getWay(); $clsMaze->output($outputText); echo '<a href="'.$outputText.'">'.$outputText.'</a>'; ?> </pre>
NORTHとかバカじゃないのwwwまとめろよwww
って自分でも思うけど、まとめる方法を忘れてしまったので・・・
配列にしてforeachするだけでもしておいたほうがよかったなーこれ。
あとは書きながら考えてるので変数名の整合性が取れてなかったりとかよくありますね〜。
↑実務でも同じこと起きるのでウンコ
しかし30分とかで素敵なの書いちゃう人は別格だなーと思います。