java - Greedy recursive search -
so trying implement groupsize method , helper functions. here 1 idea: set local set of spots hold spots you’ve found far in cluster. current spot-position, greedily add many direct neighbor spots possible. each neighbor spot newly-found, call recursively position.
i lost how go , implement method , better explanation helper functions for.
public class grid { private boolean[][] grid = null; /** * simple constructor * * @param ingrid * two-dimensional array of boolean used grid * search */ public grid(boolean[][] ingrid) { grid = ingrid; } /** * main method, creates grid, asks size of group * containing given point. */ public static void main(string[] args) { int = 0; int j = 0; // make sure we've got right number of arguments if (args.length != 2) { system.err.println("incorrect arguments."); printusage(); return; } else { = integer.parseint(args[0]); j = integer.parseint(args[1]); } // usage: java grid 3 7 search (3, 7), top occupied square // of l-shaped group of figure 7.30, pg. 281 boolean[][] griddata = { { false, false, false, false, false, false, false, false, false, true }, { false, false, false, true, true, false, false, false, false, true }, { false, false, false, false, false, false, false, false, false, false }, { false, false, false, false, true, false, false, true, false, false }, { false, false, false, true, false, false, false, true, false, false }, { false, false, false, false, false, false, false, true, true, false }, { false, false, false, false, true, true, false, false, false, false }, { false, false, false, false, false, false, false, false, false, false }, { false, false, false, false, false, false, false, false, false, false }, { false, false, false, false, false, false, false, false, false, false } }; grid mygrid = new grid(griddata); int size = mygrid.groupsize(i, j); system.out.println("group size: " + size); } /** * prints out usage message */ private static void printusage() { system.out.println("usage: java grid <i> <j>"); system.out .println("find size of cluster of spots including position i,j"); } /** * calls recursive method find group size * * @param * first index grid (i.e. row number) * @param j * second index grid (i.e. col number) * @return size of group */ public int groupsize(int i, int j) { // implement function which, among other calls helper recursive function // find group size. } /** * nested class represent filled spot in grid */ private static class spot { int i; int j; /** * constructor spot * * @param * i-coordinate of spot * @param j * j-coordinate of spot */ public spot(int i, int j) { this.i = i; this.j = j; } /** * tests whether spot equal (i.e. has same coordinates) * * * @param o * object * @return true if o spot same coordinates */ public boolean equals(object o) { if (o == null) return false; if (o.getclass() != getclass()) return false; spot other = (spot) o; return (other.i == i) && (other.j == j); } /** * returns int based on spot's contents * way: (new integer(i)).hashcode()^(new integer(j)).hashcode(); */ public int hashcode() { return << 16 + j; // combine , j 2 halves of int } /** * returns string representing spot */ public string tostring() { return "(" + + " , " + j + ")"; } } }
Comments
Post a Comment