経路数

input.txt

S---+---+
|   |   |
|   x   |
|   |   |
+---+---+
|   |   |
|   |   |
|   |   |
+---+---G

labyrinth.php

<?php

# php labyrinth.php input.txt

$data = file_get_contents(dirname(__FILE__) . '/' . $argv[1]);
$labyrinth = new LabyrinthRoute($data);
echo "経路数: " . $labyrinth->getGoalRouteCount() . "\n";

class LabyrinthRoute {
  const DISTANCE = 3;

  private $labyrinthMap = array(); // 2 次元配列 迷路テキストデータ
  private $routeMap     = array(); // 2 次元配列 道順カウント
  private $width        = 0;
  private $height       = 0;

  public function __construct($data) {
    $rows = explode("\n", $data);
    $this->height = count($rows);
    foreach ($rows as $row) {
      $this->width = strlen($row);
      $rowMap = array();
      for ($i = 0; $i < strlen($row); $i++) {
        $rowMap[] = $row[$i];
      }
      $this->labyrinthMap[] = $rowMap;
    }

    for ($y = 0; $y < $this->height; $y++) {
      $rowMap = array();
      for ($x = 0; $x < $this->width; $x++) {
        $rowMap[] = 0;
      }
      $this->routeMap[] = $rowMap;
    }
  }

  public function getGoalRouteCount() {
    // routeMap に道順を記録する
    // ここでの $jx と $jy は、分岐点（junction）を示している
    for ($jy = 0; $jy < $this->height / self::DISTANCE; $jy++) {
      for ($jx = 0; $jx < $this->width / self::DISTANCE; $jx++) {
        $y = $jy * (self::DISTANCE + 1);
        $x = $jx * (self::DISTANCE + 1);
        $this->routeMap[$y][$x] = $this->getRouteTopCount($x, $y) + $this->getRouteLeftCount($x, $y);
        // echo $this->routeMap[$y][$x] . "({$x},{$y}) ";
      }
      // echo "\n";
    }

    return $this->routeMap[$this->height - 1][$this->width - 1];
  }

  private function getRouteLeftCount($x, $y) {
    // 配列外の場合
    if (!isset($this->labyrinthMap[$y][$x - 2]) || !isset($this->labyrinthMap[$y][$x - 4])) {
      return 0;
    }

    // 通行止めの場合
    if ($this->labyrinthMap[$y][$x - 2] == 'x') {
      return 0;
    }

    // スタート地点の場合
    if ($this->labyrinthMap[$y][$x - 4] == 'S') {
      return 1;
    }

    // 既に道順が記録されている場合
    if (is_numeric($this->routeMap[$y][$x - 4])) {
      return $this->routeMap[$y][$x - 4];
    }

    return 0;
  }

  private function getRouteTopCount($x, $y) {
    // 配列外の場合
    if (!isset($this->labyrinthMap[$y - 2][$x]) || !isset($this->labyrinthMap[$y - 4][$x])) {
      return 0;
    }

    // 通行止めの場合
    if ($this->labyrinthMap[$y - 2][$x] == 'x') {
      return 0;
    }

    // スタート地点の場合
    if ($this->labyrinthMap[$y - 4][$x] == 'S') {
      return 1;
    }

    // 既に道順が記録されている場合
    if (is_numeric($this->routeMap[$y - 4][$x])) {
      return $this->routeMap[$y - 4][$x];
    }

    return 0;
  }
}