Re: Depth First Search of a Char_Matrix?

[Shark8 <onewingedshark@gmail.com>]

On Saturday, April 27, 2013 8:09:10 AM UTC-6, Alex wrote:
> Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  
> 
> 
> WW.BB
> .WWWW
> WWBBB
> BBBWW
> WWBW.
> 
> 
> In this example there are 11 alive white piece and 2 alive black pieces.
> 
> Can anyone provide any insight into this problem?

According to your definition though all of the pieces should be alive; you forgot to add in the condition that the alive piece next to them has to be the same color to transmit 'alive'.

Anyway, here's the basic layout for a DFS function on determining if they're alive... the solution is simple, instead of merely returning a boolean you want to increment a counter. Note that this is coded as you said about alive being transmitted via another alive piece sou you'll have to add that logic in, too. 
    
    Type Piece_Color is (Black, White);
    Type Piece is record
	Color : Piece_Color;
    end record;
    
    SubType Board_Range is Positive Range 1..5;
    Type Board_Type is Array(Board_Range,Board_Range) of Access Piece;

    Board : Board_Type:= (others => (others => Null));
    
    Function Is_Alive(	Board	: Board_Type;
			X, Y	: Board_Range
		      ) return Boolean is
	Use Type System.Address;
	Package Address_List_Package is New Ada.Containers.Indefinite_Vectors(
		Index_Type	=> Positive,
		Element_Type	=> System.Address);

	Address_List : Address_List_Package.Vector;
	Function Recursion(X,Y : Board_Range) Return Boolean is
	begin
	    if Board(X,Y) = null then
		Return True;
	    elsif Address_List.Contains( Board(x,Y)'Address ) then
		Return False;
	    else
		Address_List.Append( Board(X,Y).all'Address );
		Return Result : Boolean := False do
		    declare
			xs : Array (1..2) of Natural:= (x - 1, x + 1);
			ys : Array (1..2) of Natural:= (y - 1, y + 1);
		    begin
			for index_1 of ys loop
			    for index_2 of xs loop
				if index_1 in Board_Range and index_2 in Board_Range then
				    Result:= Recursion(index_2, index_1);
				end if;
				if Result then Return; end if;
			    end loop;
			end loop;
		    end;
		end return;
	    end if;
	end Recursion;
	  
    begin
	Return Recursion(x,y);
    End Is_Alive;