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

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

Re: depth first search

Show all headers | View raw

willmann817@gmail.com wrote:

> So what I gather from your post is that if I am
> starting off at (x,y) that I need to do a recursive call on (x-1,y) ,
> (x+1,y) , (x, y+1) and (x,y-1).  

Yes, that's what Barb was saying, and that corresponds to the line:

   for each neighbor W of vertex

in your template below. But I think that should really be:

   for each _unvisited_ neighbor W of vertex

> / / / / / / / 
> / 0 0 * 1 1 / 
> / * 0 0 0 0 / 
> / 0 0 1 1 1 /
> / 1 1 1 0 0 /
> / 0 0 1 0 * /
> / / / / / / /

(FTFY)

> So really my starting place will be (2,2)

Why? I don't understand what's special about that grid location.

> and I will search (1,2), (3,2) (2,1) and (2,3).  So my idea was to
> change the 0's and 1's to some other character (but not the same
> character) if they are alive (this will tell me I have visited those
> spots) and dead spots I have visited will also be changed to a
> character to know I have visited them.  But the problem is if i start
> at (2,2) above and mark that first spot dead I still need to come
> back and change it to alive after I have visited the spot below it or
> the spot 2 to the right of it.  (Because liveness is contagious with
> similar colors).  

Your problem makes it sound like maybe you shouldn't actually change
the value of the piece at each location to determine whether or not a
square has been visited. You might consider maintaining a separate 2D
array of Boolean that helps you keep track of which squares have and
have not been visited as you do the depth-first traversal.

> Can you maybe provide some more specific assistance.  

Probably not, since I don't play Go and I don't really understand what
you're trying to do from your description. From Wikipedia, and as
Markspace has pointed out, it looks like what you really want to do is
find continguous chains of same-colored pieces. Using DFS for this is
fine, but then your template ought to really read:

   for each unvisited, same-colored neighbor W of vertex

Meanwhile, it sounds like you'll need to keep track of the adjacent
unoccupied locations you come across as you traverse the group, but I
don't play Go, so I don't know how this information is used to
determine if a group is "alive" or "dead". Markspace suggests that as
long as there is any open adjacent location the group is alive, but
Wikipedia suggests that there needs to be at least two internal "eyes"
to make a group "alive", so I dunno. That sounds like the

  Application SPecific Processing goes here

part of your template, though. During each visit, search for/count
adjacent unoccupied (and probably not previously counted) locations; or
check for an eye; or whatever application-specific processing is needed
to determine deadness/aliveness.

Good luck.

Alex

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next 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