Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

Re: depth first search

Show all headers | View raw

On Sunday, April 28, 2013 10:43:33 PM UTC-4, Joshua Cranmer 🐧 wrote:
> 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

Joshua, That makes a ton of sense.  I appreciate it.  Best answer yet!

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Find similar | Unroll thread

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