From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: a07f3367d7,a9916530bf157e77 X-Google-Attributes: gida07f3367d7,public,usenet X-Google-NewGroupId: yes X-Google-Language: ENGLISH,ASCII-7-bit X-Received: by 10.224.10.6 with SMTP id n6mr30465321qan.4.1367076959968; Sat, 27 Apr 2013 08:35:59 -0700 (PDT) X-Received: by 10.50.153.41 with SMTP id vd9mr794469igb.9.1367076959577; Sat, 27 Apr 2013 08:35:59 -0700 (PDT) Path: ef9ni25954qab.0!nntp.google.com!s14no119589qam.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sat, 27 Apr 2013 08:35:59 -0700 (PDT) In-Reply-To: <87c89205-7fee-4d88-b4ab-08d26c03219b@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=69.20.190.126; posting-account=lJ3JNwoAAAAQfH3VV9vttJLkThaxtTfC NNTP-Posting-Host: 69.20.190.126 References: <87c89205-7fee-4d88-b4ab-08d26c03219b@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Depth First Search of a Char_Matrix? From: Shark8 Injection-Date: Sat, 27 Apr 2013 15:35:59 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2013-04-27T08:35:59-07:00 List-Id: 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' repres= ents 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 pie= ce is Alive is if it horizontally or vertically next to a '.' OR if it is h= orizontally or vertically next to another piece that is alive. You can thin= k of aliveness as being contagious. How can I use depth first search to co= unt the number of alive black pieces and alive white pieces? =20 >=20 >=20 > WW.BB > .WWWW > WWBBB > BBBWW > WWBW. >=20 >=20 > In this example there are 11 alive white piece and 2 alive black pieces. >=20 > 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'r= e alive... the solution is simple, instead of merely returning a boolean yo= u want to increment a counter. Note that this is coded as you said about al= ive being transmitted via another alive piece sou you'll have to add that l= ogic in, too.=20 =20 Type Piece_Color is (Black, White); Type Piece is record Color : Piece_Color; end record; =20 SubType Board_Range is Positive Range 1..5; Type Board_Type is Array(Board_Range,Board_Range) of Access Piece; Board : Board_Type:=3D (others =3D> (others =3D> Null)); =20 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 =3D> Positive, Element_Type =3D> System.Address); Address_List : Address_List_Package.Vector; Function Recursion(X,Y : Board_Range) Return Boolean is begin if Board(X,Y) =3D 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 :=3D False do declare xs : Array (1..2) of Natural:=3D (x - 1, x + 1); ys : Array (1..2) of Natural:=3D (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:=3D Recursion(index_2, index_1); end if; if Result then Return; end if; end loop; end loop; end; end return; end if; end Recursion; =20 begin Return Recursion(x,y); End Is_Alive;