Categories
General

Max Connected Colors in a Grid


    
class Solution {

  public $gridNumberRows;
  public $gridNumberCols;
  public $grid;

  public function __construct() 
  {
  
  }

  public function maxConnectedColorValue(array $grid) : int
  {
     $this->grid = $grid;
    print $this->gridNumberRows = count($grid);
    $countCol = 0;
    foreach ($grid[0] as $col)
    {
      $countCol++;
    }
      
      print "\n\r";
   print  $this->gridNumberCols = $countCol;
    
      
      
    # visted cells to false
    for($r = 0; $r < $this->gridNumberRows ; $r++) {
      for($c = 0; $c < $this->gridNumberCols ; $c++)  {
        $visited[$r][$c] = false;
      }
    }

   
    $hashmapColor = [];
    for($row = 0; $row < $this->gridNumberRows ; $row++) {
      for($col = 0; $col < $this->gridNumberCols ; $col++)  {
        
        
        if($visited[$row][$col] === true) {
          continue;
        }

        
        if($grid[$row][$col] === ''){
          $visited[$row][$col] = true;
          continue;
        }

        $cellColor= $grid[$row][$col];
        $visited[$row][$col] = true;
        if(!array_key_exists($cellColor, $hashmapColor)) {
          $hashmapColor[$cellColor] = 1;
        }
        
        $this->dfs($row, $col, $visited, $hashmapColor);
        
        
        
      }
    }    
    var_dump($hashmapColor);
    return max($hashmapColor);
  }
  
    public function dfs($r, $c, &$visited, &$hashmapColor)
    {
      
      $cellColor = $this->grid[$r][$c];
        if($cellColor == '')
            return;
                
                
      # structure [R,C]
      $neighborInstruction = [[-1,0],[0,1],[1,0],[0,1]];
      
      foreach ($neighborInstruction as $neighbor) 
      {
        $neighborRow = $neighbor[0];
        $neighborCol = $neighbor[1];
        
    

          
          
          
        #if whithin boundaries
        if(((($neighborRow + $r) >= 0) && ($neighborRow + $r) < $this->gridNumberRows)
          && ($neighborCol + $r) >= 0 && ($neighborCol + $r) < $this->gridNumberCols)
        {
        
          # check same color
          if($this->grid[$neighborRow + $r][$neighborCol + $c] === $this->grid[$r][$c] 
            && $visited[$neighborRow + $r][$neighborCol + $c] === false) {
            
              if (array_key_exists($cellColor, $hashmapColor)) {
                $hashmapColor[$cellColor] += 1;
            } 

            $visited[$r][$c] = true;
            $this->dfs($neighborRow + $r, $neighborCol + $c, $visited, $hashmapColor);

          }
        }
        
      }
    }

  
}



$grid = [
['','r','b',''],
['','b','b','b'],
['','','b','']];

$solution = new Solution();
$res = $solution->maxConnectedColorValue($grid);

var_dump($res);

Leave a Reply