Re: Depth First Search of a Char_Matrix?

[Alex <willmann817@gmail.com>]

On Saturday, April 27, 2013 7:34:51 PM UTC-4, Shark8 wrote:
> When you print the array out you have a representation of nodes (and implicitly edges), just displayed in a tabular ASCII format.
> 
> 
> 
> Is a very real sense (1,1), (1,2),...,(5,5) are merely addresses/locations of a node, wherein 'B', 'W' and '.'/' ' denote that node's state the edges, then, ar nothing more than the relationship of what is adjacent in the horizontal/vertical.
> 
> 
> 
> -------------------------------------------
> 
> [Non-DFS method]
> 
> You could count the dead pieces as follows:
> 
> if there are no empty locations all are dead, otherwise
> 
> (1) make two lists of nodes A & B,
> 
> (2) add all the empty nodes to A,
> 
> (3) for each node of A, add its neighbors to B if they are occupied,
> 
> (4) clear A
> 
> (5) for each of those nodes in B, add only its neighbors containing a piece of the same color to A
> 
> (6) merge A into B
> 
> (7) repeat #4/#5/#6 until the sizes B is the same as it was in #4.
> 
> 
> 
> At this point the system is stable and you have all the live pieces in your list, anything not in your list is then dead. -- This would be a horrible way to do things on any large sized board because of the reiterations... but it's already given you the secret of how to do it with DFS.

This is what I have so far but I am going out of Bounds and I am not sure why??

   function Count_Alive(Board : Char_Matrix) return Integer is
	M : Char_Matrix := Board; 
	V : Bool_Matrix(2..Board'Length-1, 2..Board'Length-1) := (others => (others => False));	
	WhiteCount, BlackCount : Integer := 0;
		procedure DFS(X,Y:Integer; Char : Character) is
		current : Character:= Char;	
		begin
			Put_Line("X = " & X & " Y = " & Y);
			if V(X,Y) = True or M(X,Y) = '/' or M(X,Y) /= current  then
				null;
			else
				V(X,Y) := True;
				if current = 'W' then
					WhiteCount := WhiteCount + 1;
				end if;
				
				if current = 'B' then
					BlackCount := BlackCount + 1;
				end if;
			end if;
				
				DFS(X,Y-1,current);
				DFS(X+1,Y,current);
				DFS(X-1,Y,current);
				DFS(X,Y+1,current);
				
		end DFS;

	begin
		for R in 2..M'Length(1)-1 loop
			for C in 2..M'Length(2)-1 loop
				if M(R,C) = '.' then
					DFS(R,C-1,'W');
					DFS(R+1,C,'W');
					DFS(R-1,C,'W');
					DFS(R,C+1,'W');
					
					DFS(R,C-1,'B');
					DFS(R+1,C,'B');
					DFS(R-1,C,'B');
					DFS(R,C+1,'B');
				end if;
			end loop;
		end loop;
      return (1000*BlackCount)+WhiteCount;
   end Count_Alive;