Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.

connected-cli

<?php
/*
Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.
 
 
Explanation:
Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.  

 
Input format :
 
First line of the input contains T , number of test-cases.
Then follow T testcases. Each testcase has given format.
N [ representing the dimension of the matrix N X N ].
Followed by N lines , with N numbers on each line.
 
 
 
Ouput format :
 
For each test case print one line ,  number of connected component it has.
 
Sample Input :
 
4
4
0 0 1 0
1 0 1 0
0 1 0 0
1 1 1 1
4
1 0 0 1
0 0 0 0
0 1 1 0
1 0 0 1
5
1 0 0 1 1
0 0 1 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
8
0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 0 0 1 0 1
0 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0
 
Sample output :
 
1
3
3
9
 
Constraint :
 
0 < T < 6 
0 < N < 1009 
*/

global $ppr;
	for($ppr = 0; $ppr < 100; $ppr++)
	{
	global ${'array'.$ppr};
	}
$incount = array();
$stdin = fopen('php://stdin', 'r'); //fwrite(STDOUT,  "Enter the count(INTEGER TYPE) : ");
fscanf(STDIN, "%d\n", $number);
if(!is_integer($number))
{
die("only numbers are allowed!");
}
else if(($number < 1) || ($number > 5))
{
die("Test cases should be between 1 and 5!");
}
for($ppc = 0; $ppc < $number; $ppc++)
{ //fwrite(STDOUT,  "Enter the INNER count(INTEGER TYPE) : ");
    fscanf(STDIN, "%d\n", $incount[$ppc]);
		if(!is_integer($incount[$ppc]))
		{
		die("only numbers are allowed!");
		}
		else if(($incount[$ppc] < 1) || ($incount[$ppc] > 1008))
		{
		die("N * N matrix should be beween 1 and 1008!");
		}
    ${'array'.$ppc} = array();
    
    for($ak = 0; $ak < $incount[$ppc]; $ak++)
    {
        $tem = 0;
        $hold = trim(fgets(STDIN));
        $vals = explode(" ", $hold);
        foreach($vals as $v)
        {
            $current = (int)$v;
            if(($current != 0) && ($current != 1))
            {
                fwrite(STDOUT,  "This failed is : ".$current);
                die("Please enter correct input. 0 or 1.");
            }
            ${'array'.$ppc}[$ak][$tem] = $current;
            
            ++$tem;
            if($tem > $incount[$ppc])
            {
                die("Problem with input! More than required. Reenter!");
            }
        }
		if($tem < $incount[$ppc])
		{
		  die("Problem with input! Less than required. Reenter!");
		}
        //fwrite(STDOUT, "".PHP_EOL); 
    }
}
for($ppr = 0; $ppr < $number; $ppr++)
{
		global $mat, $register, $unique , $last;
		$mat = array();
		$register = array();
		$unique = 0;

		$count = $incount[$ppr]; $last = $count - 1; $avail = 0;
		/*if($count == 0)
		{
			if(${'array'.$ppr}[0][0] == 1)
			{
			echo 1;echo "".PHP_EOL;
			}
			else
			{
			echo 0;echo "".PHP_EOL;
			}
		}
		else
		{*/
				for($a = 0; $a < $count; $a++)
				{
				   for($b = 0; $b < $count; $b++)
					{
						if(${'array'.$ppr}[$a][$b] == 1)
						{
								$avail = 0;
								foreach($register as $key=>$value)
								 {
								   if($a.",".$b == $key)
								   {
									$avail = 1;
								   }
								 }
								
									if($avail == 0)
									{
									$unique = rand(10, 90000);
									$register[$a.",".$b] = $unique;
									grphSearch($a, $b, $register, $unique, $ppr);
									}
									else
									{
									$unique = $register[$a.",".$b];
									grphSearch($a, $b, $register, $unique, $ppr);
									}
						}
					}
				}
				$register = array_unique($register);
				if(count($register) >= 1)
				{
				echo count($register);echo "".PHP_EOL;
				}
				else
				{
				echo 0;echo "".PHP_EOL;
				}
		/*}	*/				
}
function grphSearch($x, $y, $register, $unique, $ppr)
{
	for($abb = 0; $abb < 100; $abb++)
	{
	global ${'array'.$abb};
	}
	global $register, $unique, $last; $ppr;
	$a = $x;
	$b = $y;
	$temStatus  = 0;
	if(($a == 0) && ($b == 0))
	{
	  if(${'array'.$ppr}[$a][$b + 1] == 1)
	  {
		$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if($a.",".($b + 1) == $key)
		   {
			$avail = 1;  $register[$a.",".($b + 1)] = $unique;
		   }
		 }
		 
			  if($avail == 0)
			  {
			   $register[$a.",".($b + 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b] == 1)
	  {
	  
	  		$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b + 1) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b + 1)] = $unique;
			  }
	  }  
	}
	else if(($a == 0) && ($b == $last))
	{
	  if(${'array'.$ppr}[$a][$b - 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b - 1) == $key)
		   {
			$avail = 1;  $register[($a).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b - 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b - 1] == 1)
	  {  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b - 1) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b - 1)] = $unique;
			  }
	  }
	}
	else if(($a == $last) && ($b == 0))
	{
	  if(${'array'.$ppr}[$a][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b + 1) == $key)
		   {
			$avail = 1;  
			
			$unique = $value;
			$register[($a).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b + 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a - 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a-1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a - 1][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b + 1) == $key)
		   {
			$avail = 1;   $register[($a-1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b + 1)] = $unique;
			  }
	  }
	}
	else if(($a == 0) && ($b != 0) && ($b != $last))
	{
	  if(${'array'.$ppr}[$a][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b + 1) == $key)
		   {
			$avail = 1;  $register[($a).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b + 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a][$b - 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b - 1) == $key)
		   {
			$avail = 1;   $register[($a).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b - 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b + 1) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b + 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b - 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b - 1) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b - 1)] = $unique;
			  }
	  }
	}
	else if(($a != 0) && ($a != $last) && ($b == 0))
	{
	  if(${'array'.$ppr}[$a][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b + 1) == $key)
		   {
			$avail = 1;  
			
			$unique = $value;
			$register[($a).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b + 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a - 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a-1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a - 1][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b + 1) == $key)
		   {
			$avail = 1;  $register[($a-1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b + 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b + 1) == $key)
		   {
			$avail = 1;   $register[($a+1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b + 1)] = $unique;
			  }
	  }
	}
	if(($a != 0) && ($a != $last) && ($b == $last))
	{
	  if(${'array'.$ppr}[$a][$b - 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b - 1) == $key)
		   {
			$avail = 1;  $register[($a).",".($b - 1)] = $unique;
			             
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b - 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a - 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b) == $key)
		   {
			$avail = 1;   $register[($a-1).",".($b)] = $unique;
			                   
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a - 1][$b - 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b - 1) == $key)
		   {
			$avail = 1;  $register[($a-1).",".($b - 1)] = $unique;
			                 
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b - 1)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b) == $key)
		   {
			$avail = 1;   $register[($a+1).",".($b)] = $unique;
			                  
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b)] = $unique;
			  }
	  }
	  if(${'array'.$ppr}[$a + 1][$b - 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b - 1) == $key)
		   {
			$avail = 1;  $register[($a+1).",".($b - 1)] = $unique;
			               
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b - 1)] = $unique;
			  }
	  }
	}
	else if(($a == $last) && ($b != 0) && ($b != $last))
	{
	  if(${'array'.$ppr}[$a][$b - 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b - 1) == $key)
		   {
			$avail = 1;
			$register[($a).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b - 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a][$b + 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b + 1) == $key)
		   {
			$avail = 1;  
			
			$unique = $value;
			$register[($a).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b + 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a - 1][$b] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b) == $key)
		   {
			$avail = 1;  $register[($a-1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a - 1][$b - 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b - 1) == $key)
		   {
			$avail = 1; $register[($a-1).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b - 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a - 1][$b + 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b + 1) == $key)
		   {
			$avail = 1;  $register[($a-1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b + 1)] = $unique;
			  }
	  }
	  
	}
	else if(($a != 0) && ($a != $last) && ($b != 0) && ($b != $last))
	{
	  if(${'array'.$ppr}[$a][$b + 1] == 1)
	  {
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b + 1) == $key)
		   {
			$avail = 1;  
			
			$unique = $value;
			$register[($a).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b + 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a][$b - 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a).",".($b - 1) == $key)
		   {
			$avail = 1; $register[($a).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a).",".($b - 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a - 1][$b] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b) == $key)
		   {
			$avail = 1; $register[($a - 1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a - 1][$b - 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b - 1) == $key)
		   {
			$avail = 1; $register[($a - 1).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b - 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a - 1][$b + 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a-1).",".($b + 1) == $key)
		   {
			$avail = 1; $register[($a - 1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a-1).",".($b + 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a + 1][$b] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b) == $key)
		   {
			$avail = 1; $register[($a + 1).",".($b)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a + 1][$b + 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b + 1) == $key)
		   {
			$avail = 1; $register[($a + 1).",".($b + 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b + 1)] = $unique;
			  }
	  }
	  
	  if(${'array'.$ppr}[$a + 1][$b - 1] == 1)
	  {
	  
	  	$temStatus = 1;
		$avail = 0;
		foreach($register as $key=>$value)
		 {
		   if(($a+1).",".($b - 1) == $key)
		   {
			$avail = 1; $register[($a + 1).",".($b - 1)] = $unique;
		   }
		 }
			  if($avail == 0)
			  {
			   $register[($a+1).",".($b - 1)] = $unique;
			  }
	  }
	  
	}
	
	if($temStatus == 0)
	{}
	else
	{
	$register[$x.",".$y] = $unique;
	} 
}
?>