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

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

Re: depth first search

Show all headers | View raw

willm...@gmail.com wrote:
 ... [snip] ...  
> Thanks for your help! But I need to clarify a few things if it is not too much trouble. 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).  So for example:
> 
> / / / / / / /
> / 00*11  /
> / *0000  /
> / 00111  /
> / 11100  /
> / 0010*  /
> / / / / / / /

Be careful. The representation is not the model. 

> Imagine 0's are white and 1's are black and * is an empty space.  Also image that the matrix also is a 
> 7x7 and not a 5 by 5 where the above diagram is surrounded by '/' to make sure you don't get an 
> index out of bounds error.  So really my starting place will be (2,2) 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).  
> Can you maybe provide some more specific assistance.  This is HW and I do not want the answer but I 
> have been cracking away at this on scratch paper with pictures and diagrams but still am a little 
> stuck.

Advice #1: Let go of the name of a specific algorithm. If you don't know what "depth" is, 
latching onto "depth-first" won't be of much use. Others have suggested a better algorithm.

Instead of imprinting on some magical algorithm label, think about the problem in its raw 
structures. What is a 'Board'? 

It's a collection of 19 by 19 labeled intersections, yes?

What do "characters" have to do with that model? Think in terms of the problem itself, 
and not in terms of predetermined algorithms or representations.

Java has the power to directly express notions like 'Board' and 'Intersection', and the 
attributes each type has, like 'Stone stone;', where 'Stone' is a type (hint: enum) with 
two values, 'BLACK' and 'WHITE'. (You should know the naming conventions.)

So forget using dumb old characters to mean something other than "character".

There are lots of ways to express collections of things like "rows" and "collections", and 
"arrays of rows" and "collections of rows", for example, or even just 
"collections/arrays of 'Intersection'".

One 'Intersection' instance can know an awful lot about itself. For example, it can know 
the indexes (0 through 18, inclusive) of the row and column of each of its neighbors, as 
well as its own.

It can have a type to represent its liveness or connectedness state. For example, a type 
'Liveness' (hint: enum) can represent states of 'LIVE', 'DEAD' or 'UNKNOWN'. (You could also 
represent 'UNKNOWN' by having 'null' for an instance value of 'Liveness'.)

So please answer to this group with a type design for 'public class Intersection'.

You can use constant variables (not actually a contradiction in Java) to hold things like 
board size. So to give you a boost, actually maybe too much, here's the sort of thing I have 
in mind (using 'class' instead of 'interface', though the latter could be better):

public class Board 
{
  public static final int BOARD_SIZE = 19;

  final Intersection [] [] intersections = new Intersection [BOARD_SIZE] [BOARD_SIZE];

  /**
   * Constructor.
   */
  public Board() 
  {
    for (int row = 0; row < intersections.length; ++row)
    {
      for (int column = 0; column < row.length; ++column)
      {
        intersections [row] [column] = new Intersection();
      }
    }
  }

// etc.
}

Looking forward to your ideas for 'Intersection'.

-- 
Lew

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