Groups > comp.lang.java.programmer > #23710

Re: depth first search

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx05.eternal-september.org!.POSTED!not-for-mail
From	Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid>
Newsgroups	comp.lang.java.programmer
Subject	Re: depth first search
Date	Sun, 28 Apr 2013 21:43:33 -0500
Organization	A noiseless patient Spider
Lines	45
Message-ID	<klkmip$tph$1@dont-email.me> (permalink)
References	<77f5a380-09d9-4054-b26f-22b32424b504@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding	7bit
Injection-Date	Mon, 29 Apr 2013 02:40:25 +0000 (UTC)
Injection-Info	mx05.eternal-september.org; posting-host="95ab4c362dcce54022543f80bbbb46d3"; logging-data="30513"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/8tYP1hw71oEbE9sHoDeKuIaa5bzrr16Q="
User-Agent	Mozilla/5.0 (Windows NT 6.1; WOW64; rv:21.0) Gecko/20100101 Thunderbird/21.0
In-Reply-To	<77f5a380-09d9-4054-b26f-22b32424b504@googlegroups.com>
Cancel-Lock	sha1:x2UXVLBwIjh/5MkQX1EVEkNQgps=
Xref	csiph.com comp.lang.java.programmer:23710

Show key headers only | View raw

On 4/27/2013 11:46 PM, willmann817@gmail.com wrote:
> I am given method signature that takes a square 2D Character Array (a
> matrix) that represents a board of a game called Go.  The board has
> black pieces represented by a 'B' white pieces represented by a 'W'
> and empty spaces represented by '.' The board also has a padding to
> represent going off the board this padding on all sides is
> represented by the character '/'.  A piece is considered alive if it
> is horizontally or vertically next to an empty space and alive pieces
> are contagious to other alive pieces of the same color. Using depth
> first search how can I count the number of alive black pieces and
> alive white pieces?  I only know how to use DFS on a graph data type
> not a 2D array.

The algorithm you are looking for is more properly called the "flood 
fill" algorithm; the name is derived from the notion that filling the region

Note that a 2-D grid is itself a graph; the adjacency lists are just 
implicit in the definition. Consider:

o-o-o-o
| | | |
o-o-o-o
| | | |
o-o-o-o
| | | |
o-o-o-o

[Note that you need fixed-width fonts for the above diagram to make any 
sense.]

If that still isn't enough for you, consider that you want to find the 
connected components of a graph where edges between differently-colored 
nodes are deleted, e.g.:

B-B W-W
|   | |
B W-W-W
|
B * B-B
| |
B *-*-*

-- 
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

Thread

depth first search willmann817@gmail.com - 2013-04-27 21:46 -0700
  Re: depth first search Barb Knox <see@sig.below> - 2013-04-28 21:06 +1200
    Re: depth first search "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-04-28 11:40 +0100
      Re: depth first search willmann817@gmail.com - 2013-04-28 07:22 -0700
        Re: depth first search "Alex" <foo@email.invalid> - 2013-04-28 20:25 +0000
          Re: depth first search Lew <lewbloch@gmail.com> - 2013-04-28 19:01 -0700
        Re: depth first search Lew <lewbloch@gmail.com> - 2013-04-28 18:42 -0700
          Re: depth first search Barb Knox <see@sig.below> - 2013-04-29 13:59 +1200
            Re: depth first search lipska the kat <"nospam at neversurrender dot co dot uk"> - 2013-04-29 11:21 +0100
              Re: depth first search Barb Knox <see@sig.below> - 2013-05-02 16:02 +1200
  Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 12:22 -0700
  Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 12:49 -0700
    Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 16:21 -0700
  Re: depth first search Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2013-04-28 21:43 -0500
    Re: depth first search willmann817@gmail.com - 2013-04-29 08:46 -0700

csiph-web