Code of turi
<?php
require_once('map.class.php');
$mapFile = (isset($_REQUEST['map'])) ? $_REQUEST['map'] : 'map.txt';
$destinationFile = (isset($_REQUEST['dest'])) ? $_REQUEST['dest'] : 'dest.txt';
$myMap = new BigMap($mapFile, $destinationFile);
$smallMap = new SmallMap();
$myMap->makeSmallMap($smallMap);
$smallMap->start();
$smallMap->echhho();
?>
<?
// *************************************************************
// INCLUDE FILE PASTED BELOW FOR DISPLAY ON PHP-EDITORS.COM
// *************************************************************
// MAP.CLASS.PHP
?><?php
class Map {
var $ways = Array();
var $destination = Array();
var $allDestination = Array();
function addWay($from, $distance, $to) {
if ($from == $to) return;
$length = sizeof($this->ways);
for ($i=0; $i<$length; $i++) {
if ($this->ways[$i]['from'] == $from and $this->ways[$i]['to'] == $to) {
if ($this->ways[$i]['distance'] > $distance) {
$this->ways[$i]['from'] = $from;
$this->ways[$i]['distance'] = $distance;
$this->ways[$i]['to'] = $to;
}
return;
}
}
array_push($this->ways, array('from' => $from, 'distance'=> $distance, 'to' => $to));
array_push($this->allDestination, $from, $to);
}
function addDestination($dest) {
if (!in_array($dest, $this->allDestination)) die('error: '.$dest);
if (!in_array($dest, $this->destination)) array_push($this->destination, $dest);
}
function getWaysIndex($from) {
$indexs = Array();
$length = sizeof($this->ways);
for ($i=0; $i<$length; $i++) {
if ($this->ways[$i]['from'] == $from)
array_push($indexs, $i);
}
return $indexs;
}
};
class BigMap extends Map {
function BigMap($mf, $df) {
$file = @fopen($mf, 'r') or die('fopen error: '.$mf);
while (!feof($file)) {
$buffer = fgets($file, 512);
$array = explode(' ', trim($buffer));
if (sizeof($array) == 4) {
$this->addWay($array[0], $array[1], $array[2]);
if ($array[3] == 2) {
$this->addWay($array[2], $array[1], $array[0]);
}
}
}
fclose($file);
$file = @fopen($df, 'r') or die('fopen error: '.$df);
while (!feof($file)) {
$buffer = fgets($file, 512);
$array = explode(' ', trim($buffer));
foreach($array as $item) {
if (!empty($item))
$this->addDestination( strtoupper($item) );
}
}
fclose($file);
}
function makeSmallMap(&$map) {
foreach ($this->destination as $dest) {
$this->make($map, array($dest), 0);
}
}
function make(&$map, $way, $dist) {
$dest = $way[count($way)-1];
$from = $way[0];
$index = $this->getWaysIndex($dest);
foreach($index as $i) {
$to = $this->ways[$i]['to'];
if (in_array($to, $way)) continue;
$distance = $this->ways[$i]['distance'] + $dist;
if ( in_array($to,$this->destination) ) {
$map->addWay($from, $distance, $to);
} else {
array_push($way, $to);
$this->make($map, $way, $distance);
array_pop($way);
}
}
$map->addDestination($from);
}
}
class SmallMap extends Map {
var $path = Array();
var $sumPathDist = 0;
var $optPathDist = -1;
var $pathNumber = 0;
var $run = true;
function Start() {
$length = sizeof($this->destination);
for ($i=0; $i<$length; $i++) {
array_push($this->path,
array( 'path' => array($this->destination[$i]),
'distance' => 0,
'absent' => $length-1 )
);
$this->pathNumber++;
}
while ($this->run) {
$this->oneStep();
}
}
function oneStep() {
$this->run = false;
$length = sizeof($this->path);
for ( $i=0; $i<$length; $i++ ) {
if ( $this->path[$i] == null ) {
continue;
}
if ( $this->optPathDist != -1 and $this->path[$i]['distance'] > $this->optPathDist ) {
$this->sumPathDist -= $this->path[$i]['distance'];
$this->path[$i] = null;
$this->pathNumber--;
continue;
}
if ( $this->path[$i]['absent'] == 0 ) {
continue;
}
$pathMin = ($this->optPathDist!=-1)?$this->optPathDist:($this->sumPathDist/$this->pathNumber);
if ( $this->path[$i]['distance'] <= $pathMin) {
$a = $this->getWaysIndex($this->path[$i]['path'][sizeof($this->path[$i]['path'])-1]);
$first = true;
$oldPath = $this->path[$i]['path'];
$oldDistance = $this->path[$i]['distance'];
$oldAbsent = $this->path[$i]['absent'];
foreach($a as $b) {
$newDistance = $this->ways[$b]['distance'];
if ( $this->optPathDist != -1 and $oldDistance+$newDistance > $this->optPathDist ) {
continue;
}
$newDestination = $this->ways[$b]['to'];
if ($this->isRound($oldPath, $newDestination) ) {
continue;
}
$this->run = true;
if ($first) {
$index = $i;
$first = false;
} else {
$index = sizeof($this->path);
array_push($this->path,
array( 'path' => $oldPath,
'distance' => $oldDistance,
'absent' => $oldAbsent )
);
$this->sumPathDist += $oldDistance;
$this->pathNumber++;
}
if (!in_array($newDestination, $this->path[$index]['path'])) {
$this->path[$index]['absent'] -= 1;
}
array_push($this->path[$index]['path'], $newDestination);
$this->path[$index]['distance'] += $newDistance;
$this->sumPathDist += $newDistance;
if ( $this->optPathDist == -1 and $this->path[$index]['absent'] == 0 ) {
$this->optPathDist = $this->path[$index]['distance'];
} elseif ( $this->path[$index]['absent'] == 0 and $this->path[$index]['distance'] < $this->optPathDist ) {
$this->optPathDist = $this->path[$index]['distance'];
}
}
if ($first and $oldAbsent > 0) {
$this->run = true;
$this->path[$i] = null;
$this->sumPathDist -= $oldDistance;
$this->pathNumber--;
}
}
}
}
function isRound(&$path, &$newDest) {
$length = sizeof($path);
$index = -1;
for ($i=0; $i<$length; $i++) {
if ($path[$i] == $newDest) $index = $i;
}
if ($index == -1) return false;
for ($i=$index+1; $i<$length; $i++) {
for ($j=0; $j<$index; $j++) {
if ($path[$j] == $path[$i]) continue;
if ($j == $index-1) return false;
}
}
return true;
}
function echhho() {
foreach($this->path as $k => $i)
if ($i['path'] != null)
echo join(' ', array_unique($i['path'])).' '.$i['distance']."\n";
}
};
?>
Back to results
|
|
