java - Determine number of grouped values within a grid -

was wondering if me logic.

say have grid consists of:

  1 2 3 1 b 2 b b 3 a b 

there 3 groups in grid, determined each cell's value , neighboring cells have same value, assuming coordinate scheme (col, row):

group 1: (1, 1), (1, 2), (1, 3), (2, 3) has value of a

group 2: (2, 1), (2, 2), (3, 2), (3, 3) has value of b

group 3: (3, 1) has value of a

could suggest how determine programmatically?

i thinking along lines of:

• use loop iterate through grid
  • have method checks cell's top, right, bottom , left cell's value (also accounting boundary cells)
    • check if cell of same value, store somehow
    • otherwise new group?
  • recurse

but can't around if finds cell different value. think i'm on complicating simple solution here.

i ideally store array of coordinates relate groups within grid.

i think conceptually easiest way handle recursion. granted, because of java's subpar tail-recursion support, iterative solution more efficient; still, recursion should work smallish values.

take @ sample code

public static void main(string[] args) {     int xbound = 3;     int ybound = 3;     string[][] grid = new string[][] {         {"a", "b", "a"},         {"a", "b", "b"},         {"a", "a", "b"}      };      for(int = 0; < ybound; i++) {         for(int j = 0; j < xbound; j++) {             string state = grid[i][j];             list<list<integer>> group = getgroup(state, j, i, xbound, ybound, grid);             if (group.size() != 0) {                 system.out.println(state + " " + group);             }            }     } }  static list<list<integer>> getgroup(string state, int xindex, int yindex, int xbound, int ybound, string[][] grid) {     if (xindex >= xbound || xindex < 0 || yindex >= ybound || yindex < 0 || grid[yindex][xindex].equals("used")) {         return new arraylist<>();     } else if (grid[yindex][xindex].equals(state)){         grid[yindex][xindex] = "used";          list<list<integer>> ourposse = new arraylist<list<integer>>();         ourposse.add(arrays.aslist(yindex, xindex));         ourposse.addall(getgroup(state, xindex + 1, yindex, xbound, ybound, grid));         ourposse.addall(getgroup(state, xindex - 1, yindex, xbound, ybound, grid));         ourposse.addall(getgroup(state, xindex, yindex + 1, xbound, ybound, grid));         ourposse.addall(getgroup(state, xindex, yindex - 1, xbound, ybound, grid));          return ourposse;     } else {         return new arraylist<>();     } } 

we step through grid, trying use each entry "root" of new group. if distinct group in fact rooted @ entry (i.e. grpct != 0), print it.

in getgroupmethod, first check whether we've gone out of our grid bounds or whether we've used entry in previous group. note checking done mutating grid, keep memo instead.

otherwise, if present entry matches state we're looking group on, add entry group , expand in directions, looking other entries add group.

otherwise, know present entry can't part of group.

edit: in terms of asymptotic running time, because we're memoizing setting flag in grid , considering each entry @ 4 times, we've got o(n^2).