Code of agachi
<?
/**
* Copyright 2003 Agachi Valentin (avalyk2 AT hotmail DOT com)
*/
set_time_limit(120);
error_reporting(E_ALL);
// read input data
$map_data = file('map.txt');
$dest = file('dest.txt');
$keys = array();
for ($ch = 'A'; $ch < 'Z'; $ch++)
array_push($keys, $ch);
array_push($keys, 'Z');
// generate a 2-dimension matrix
$_keys = $keys;
foreach ($keys as $key1) {
$map[$key1] = array();
foreach ($_keys as $key2) {
$map[$key1][$key2] = array();
}
reset($_keys);
}
// insert input data in the matrix
foreach ($map_data as $map_item) {
$map_item_data = explode(' ', str_replace(array("\n", "\r"), '', $map_item));
if (count($map_item_data) == 4) {
if ($map_item_data[3] == '1') {
if (!isset($map[$map_item_data[0]][$map_item_data[2]]['len']) || ($map[$map_item_data[0]][$map_item_data[2]]['len'] > $map_item_data[1])) {
$map[$map_item_data[0]][$map_item_data[2]]['len'] = $map_item_data[1];
}
} else {
if (!isset($map[$map_item_data[0]][$map_item_data[2]]['len']) || ($map[$map_item_data[0]][$map_item_data[2]]['len'] > $map_item_data[1])) {
$map[$map_item_data[0]][$map_item_data[2]]['len'] = $map_item_data[1];
}
if (!isset($map[$map_item_data[2]][$map_item_data[0]]['len']) || ($map[$map_item_data[2]][$map_item_data[0]]['len'] > $map_item_data[1])) {
$map[$map_item_data[2]][$map_item_data[0]]['len'] = $map_item_data[1];
}
}
}
}
// Roy-Floyd algorithm to calculate the shortest paths between any 2 points in the matrix
$__keys = $_keys = $keys;
foreach ($keys as $k) {
foreach ($_keys as $i) {
foreach ($__keys as $j) {
if (($i != $j) && isset($map[$i][$k]['len']) && isset($map[$k][$j]['len']) && (!isset($map[$i][$j]['len']) || ($map[$i][$k]['len'] + $map[$k][$j]['len'] < $map[$i][$j]['len']))) {
$map[$i][$j]['len'] = $map[$i][$k]['len'] + $map[$k][$j]['len'];
$map[$i][$j]['dad'] = $k;
}
}
reset($__keys);
}
reset($_keys);
}
$dest_points = explode(' ', str_replace(array("\n", "\r"), '', $dest[0]));
$dest_count = count($dest_points);
// a recursise backtracking function to generate all the permutations of the destination points
function blah() {
global $lev, $dest_count, $dest_points, $map, $x, $v, $s, $sol, $fp, $time;
$lev++;
if ($lev == $dest_count) {
if (!isset($sol['len']) || ($s < $sol['len'])) {
$sol['len'] = $s;
$sol['path'] = $x;
}
$lev--;
return;
}
for ($i = 0; $i < $dest_count; $i++) {
if (!$v[$i] && (!isset($sol['len']) || (($lev == 0) || (($lev > 0) && ($s + $map[ $dest_points[$x[$lev - 1]] ][ $dest_points[$i] ]['len'] < $sol['len']) ))) ) {
$x[$lev] = $i; $v[$i] = 1;
if ($lev > 0) {
$s += $map[ $dest_points[$x[$lev - 1]] ][ $dest_points[$i] ]['len'];
} else {
$s = 0;
}
blah();
$x[$lev] = -1; $v[$i] = 0;
if ($lev > 0) {
$s -= $map[ $dest_points[$x[$lev - 1]] ][ $dest_points[$i] ]['len'];
} else {
$s = 0;
}
}
}
$lev--;
}
$lev = -1;
$x = $v = array();
for ($i = 0; $i < $dest_count; $i++) {
$x[$i] = -1;
$v[$i] = 0;
}
$sol = array();
$s = 0;
blah();
//print_r($sol);
// solution output
for ($i = 0; $i < $dest_count; $i++) {
echo $dest_points[$sol['path'][$i]].' ';
}
echo $sol['len'];
?>
<?
// *************************************************************
// INCLUDE FILE PASTED BELOW FOR DISPLAY ON PHP-EDITORS.COM
// *************************************************************
// FUNCS.MISC.PHP
?><?
///////////////////////////////////////
// //
// Misc Functions //
// (c) 2001 Agachi Valentin //
// //
///////////////////////////////////////
/////////////////
// Debug //
/////////////////
function d_array_as_string (&$array, $s = "", $column = 0) {
$str = "<span style=\"color:#009900\">Array $s </span>(<br />\n";
while(list($var, $val) = each($array)) {
$str .= "<span style=\"color:white\">";
for ($i = 0; $i < $column+1; $i++){
$str .= "===";
}
$str .= "</span>";
$str .= '[<span style="color:#3399CC">'.$var.'</span>] --> ';
$str .= d_wr2($val, $var, $column + 1)."<br />\n";
}
$str .= "<span style=\"color:white\">";
for ($i = 0; $i < $column; $i++){
$str .= "=====";
}
$str .= "</span>)";
reset($array);
return $str;
}
function d_object_as_string (&$object, $s = "", $column = 0) {
if (trim(get_class($object)) == "") {
return "$object";
}
else {
$str = "<span style=\"color:#009900\">Object ".get_class($object)." </span>(<br />\n";
$vars = get_object_vars($object);
while (list($var, $val) = each($vars)) {
$str .= "<span style=\"color:white\">";
for ($i = 0; $i < $column+1; $i++){
$str .= "=====";
}
$str .= "</span>";
$str .= '[<span style="color:#3399CC">'.$var.'</span>] --> ';
$str .= d_wr2($val, "", $column+1)."<br />\n";
}
$vars = get_class_methods(get_class($object));
while (list($id, $val) = each($vars)) {
$str .= "<span style=\"color:white\">";
for ($i = 0; $i < $column+1; $i++){
$str .= "=====";
}
$str .= "</span><span style=\"color:#FF0000\">";
$str .= $val."</span>()<br />\n";
}
$str .= "<span style=\"color:white\">";
for ($i = 0; $i < $column-1; $i++){
$str .= "=====";
}
$str .= "</span>)";
return $str;
}
}
function d_wr2(&$thing, $s = "", $column = 0) {
if (is_object($thing)) {
return d_object_as_string($thing, $s, $column);
}
elseif (is_array($thing)) {
return d_array_as_string($thing, $s, $column);
}
elseif (is_double($thing)) {
return "Double(<span style=\"color:#0000CC\">".$thing."</span>)";
}
elseif (is_long($thing)) {
return "Long(<span style=\"color:#0000CC\">".$thing."</span>)";
}
elseif (is_string($thing)) {
return "String(<span style=\"color:#FF00CC\">".htmlentities($thing)."</span>)";
}
elseif (is_bool($thing)) {
if ($thing)
return "Bool(<span style=\"color:#CC0000\">True</span>)";
else return "Bool(<span style=\"color:#CC0000\">False</span>)";
}
else {
return "Unknown(<span style=\"color:#CC0000\">".$thing."</span>)";
}
}
function wr(&$thing, $s = "") {
echo "<span style=\"font-family:Tahoma; font-size:8pt; font-weight:bold\">";
echo d_wr2($thing, $s);
echo "</span>";
}
//////////////////
// Timer //
//////////////////
function d_timer_start ($name = 'default') {
global $d_timer_start_times;
$d_timer_start_times[$name] = explode(' ', microtime());
}
function d_timer_stop ($name = 'default') {
global $d_timer_stop_times;
$d_timer_stop_times[$name] = explode(' ', microtime());
}
function d_timer_value ($name = 'default') {
global $d_timer_start_times, $d_timer_stop_times;
if (!isset($d_timer_start_times[$name]))
return 0;
if (!isset($d_timer_stop_times[$name]))
$stop_time = explode(' ', microtime());
else $stop_time = $d_timer_stop_times[$name];
$current = $stop_time[1] - $d_timer_start_times[$name][1];
$current += $stop_time[0] - $d_timer_start_times[$name][0];
return $current;
}
/////////////////
// Misc //
/////////////////
function post_check()
{
$accept = false;
$hoststr = "http://".$_SERVER['HTTP_HOST'].$_SERVER['PHP_SELF'];
if(substr($_SERVER['HTTP_REFERER'], 0, strlen($hoststr)) == $hoststr) $accept = true;
$hoststr = "https://".$_SERVER['HTTP_HOST'].$_SERVER['PHP_SELF'];
if(substr($_SERVER['HTTP_REFERER'], 0, strlen($hoststr)) == $hoststr) $accept = true;
return $accept;
}
function show_img($img, $style = "")
{
if ($style) $style .= ' ';
$size = @GetImageSize($img);
echo '<img src="'.$img.'" '.$size[3].' border="0" '.$style.'/>';
}
function str_strip(&$s, $strip = true, $slash = true, $trim = false)
{
if ($strip) $s = strip_tags($s);
if ($slash) $s = addslashes($s);
if ($trim) $s = trim($s);
}
function array_slash(&$array, $strip = true, $slash = true, $trim = false)
{
$keys = array_keys($array);
for($i = 0; $i < count($keys); $i++)
str_strip($array[$keys[$i]], $strip, $slash, $trim);
}
function array_format(&$array, $func)
{
$keys = array_keys($array);
for($i = 0; $i < count($keys); $i++)
$array[$keys[$i]] = $func($array[$keys[$i]]);
}
function strip_http($str)
{
$t = preg_replace("~^(http|https):\/\/(.*)\/?$~", "\\2", $str);
if ($t{strlen($t) - 1} == '/')
return substr($t, 0, strlen($t) - 1);
else return $t;
}
function roman(&$n)
{
$romans = array(1 => 'I', 2 => 'II', 3 => 'III', 4 => 'IV', 5 => 'V', 6 => 'VI', 7 => 'VII', 8 => 'VIII', 9 => 'IX', 10 => 'X', 11 => 'XI', 12 => 'XII');
return $romans[$n];
}
function str_cut($s, $limit = 16, $suffix = '...') {
return (strlen($s) <= $limit) ? $s : substr($s, 0, $limit).$suffix;
}
?>
Back to results
|
|
