daily pastebin goal
46%
SHARE
TWEET

google task

a guest Jan 27th, 2016 359 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.  
  3. class Google {
  4.     private $_input;
  5.     private $_output;
  6.  
  7.     public function __construct($input)
  8.     {
  9.         $this->_input = $this->_output = $input;
  10.     }
  11.  
  12.     public function solve(){
  13.         for($i = 0; $i < sizeof($this->_input); $i++){
  14.             for($j = 0; $j < sizeof($this->_input[$i]); $j++){
  15.                 $this->_output[$i][$j] =
  16.                     $this->_input[$i][$j] === 0
  17.                         ? $this->step($i, $j)
  18.                         : $this->_input[$i][$j];
  19.             }
  20.         }
  21.         return $this;
  22.     }
  23.  
  24.     public function result(){
  25.         return $this->_output;
  26.     }
  27.  
  28.     protected function step($i, $j, $path = array(), &$results = array()){
  29.         $path[] = $this->coordinate($i, $j);
  30.  
  31.         if($this->_input[$i][$j] === 'G'){
  32.             return sizeof($path) - 1;
  33.         }
  34.         if($this->_input[$i][$j] === 'B'){
  35.             return INF;
  36.         }
  37.  
  38.         if($this->check($i, $j + 1, $path)){
  39.             $results[] = $this->step($i, $j + 1, $path);
  40.         }
  41.         if($this->check($i, $j - 1, $path)){
  42.             $results[] = $this->step($i, $j - 1, $path);
  43.         }
  44.         if($this->check($i + 1, $j, $path)){
  45.             $results[] = $this->step($i + 1, $j, $path);
  46.         }
  47.         if($this->check($i - 1, $j, $path)){
  48.             $results[] = $this->step($i - 1, $j, $path);
  49.         }
  50.  
  51.         return min($results);
  52.     }
  53.  
  54.     protected function coordinate($i, $j){
  55.         return $i * sizeof($this->_input[$i]) + $j;
  56.     }
  57.  
  58.     protected function check($i, $j, $path){
  59.         return isset($this->_input[$i][$j]) && array_search($this->coordinate($i, $j), $path) === false;
  60.     }
  61. }
  62.  
  63. $input = array(
  64.     array( 0,   0,   0 ),
  65.     array('B', 'G', 'G'),
  66.     array('B',  0,   0 ),
  67. );
  68.  
  69. $google = new Google($input);
  70. $result = $google->solve()->result();
  71.  
  72. echo "<table border='1' cellspacing='0' cellpadding='5' style='margin-bottom: 20px;'>";
  73. foreach($result as $row){
  74.     echo "<tr><td>" . implode("</td><td>", $row) . "</td></tr>";
  75. }
  76. echo "</table>";
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top