Recursion
and Blobs

Nicholas Duchon: Feb 16, 2019.

Outline


Blob Counting

This is the Blob counting algorithm developed in DJW 2nd edition, with a few modifications to make it a little easier to see how the algorithm works.

Grid (pp 257-259) to GridND: I have modified the visited array to show the order in which the elements in the array are visited, and changed the toString method to also print this array. Also added another constructor that will accept a 2-D int array (1's as true and 0's as false) to make it possible to examine a specific array.

BlobApp (pg 260) to BlobAppND: This will support the 2-D constructor, and has a simple example. The default array size is different also.

Note that the algorithm goes in this order:

  1. up
  2. down
  3. left
  4. right

And the recursion acts like a stack, remembering branches that were taken in the search by leaving the current cell to go to the next unmarked adjacent cell in the order shown above.

The checking order here is: up --> down --> left --> right. You can follow this by starting at 1 in this example and tracing the first blob through 76, the second blob from 77 through 79 and so on.


Newer Version - GridND2:

Here are some comments about the methods:

// File: GridND2.java
// Date: Mar 18, 2017
// Author: Nicholas Duchon
// Based on Dale/Joyce/Weems Chapter 4, BlobApp.java and Grid.java

//----------------------------------------------------------------------
// BlobApp.java          by Dale/Joyce/Weems                   Chapter 4
//
// Instantiates a Grid based on a percentage probability provided by the
// user and reports the number of blobs in the Grid.
//----------------------------------------------------------------------
// Nick Duchon - modifications
// Date: Oct 5, 2008
//----------------------------------------------------------------------
// Grid.java              by Dale/Joyce/Weems                  Chapter 4
//
// Supports grid objects consisting of blob and non-blob characters.
// Allows the number of blobs it contains to be counted.
//
// Modifications by Nicholas Duchon
//----------------------------------------------------------------------

import java.util.Scanner;
import java.util.Random;

public class GridND2 {
   int rows; // number of grid rows
   int cols; // number of grid columns
    
   boolean [][] grid;     // the grid containing blobs
   int     [][] visited;  // used by blobCount
   int     [][] id;       // the id of each blob
   int index;             // number the order of visits to active cells
   int count;             // number of the visiting of a cell
  
   public static void main(String[] args) {
      Scanner conIn = new Scanner(System.in);
  
      final int GRIDR = 20;   // number of grid rows
      final int GRIDC = 20;   // number of grid columns
  
      // Get percentage probability of blob characters
      int percentage;      
      System.out.print("Input percentage probability (0 to 100): ");
      if (conIn.hasNextInt())
         percentage = conIn.nextInt();
      else {
         System.out.println("Error: you must enter an integer.");
         System.out.println("Terminating program.");
         return;
      } // end geting input from the user
     
      System.out.println();
  
      // create grid
      GridND2 grid = new GridND2 (GRIDR, GRIDC, percentage);
     
      // display grid and blob count
      int c = grid.blobCount();
      System.out.println (grid);
      System.out.println ("\nThere are " + c + " blobs.\n");
  
} // end main method

    // Preconditions: rows and cols > 0
    //                0 <= percentage <= 100
    //
    // Instantiates a grid of size rows by cols, where locations are set to
    // indicate blob characters based on the percentage probability.
   public GridND2 (int prows, int pcols, int percentage) {
      rows    = prows;
      cols    = pcols;
      grid    = new boolean [rows][cols]; // true means cell part of a blob
      visited = new int     [rows][cols]; // true if location visited
      id      = new int     [rows][cols]; // which blob?
  
      // to generate random numbers
      Random rand = new Random();
  
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            grid [i][j] = (percentage > rand.nextInt(100));
  
} // end int/int/int constructor

   public String toString() {
      String gridString = "";
      for (int i = 0; i < rows; i++) {
         for (boolean b: grid[i])
            gridString += b?"X":"-";
         gridString += "     ";
         for (int m: visited[i]) {
            gridString += String.format ("%4d", m);
         } // end for each row in the visited matrix also
         gridString = gridString + "\n";   // end of row
      } // end for each row of the grid
     
      for (int [] r: id) {
         gridString += "\n";
         for (int v: r)
            gridString += (v==0)?"  .":String.format ("%3d", v);
      } // end for each row
      return gridString;
  
} // end method toString

    // returns the number of blobs in this grid
   public int blobCount() {
      count = 0;
      index = 1;
     
      // initialize visited and id arrays
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++) {
            visited [i][j] = 0;
            id      [i][j] = 0;
         } // init visited and id arrays
       
      // count blobs
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            if (grid[i][j] && visited[i][j] == 0) {
               count++;
               markBlob(i, j);
            } // end for each unvisited blob cell
        
      return count;
  
} // end method blobCount
  
    // Mark position row, col as having been visited.
    // Check and if appropriate mark locations above, below, left,
    // and right of that position.
   private void markBlob(int row, int col) {
      if (row <  0   ) return; // these are out of grid locations
      if (row >= rows) return;
      if (col <  0   ) return;
      if (col >= cols) return;
     
      if (!  grid [row][col]     ) return; // not in blobs
      if (visited [row][col] != 0) return; // already visited
     
      visited [row][col] = index++;
      id      [row][col] = count;
     
      markBlob(row - 1, col    ); // up
      markBlob(row + 1, col    ); // down
      markBlob(row    , col - 1); // left
      markBlob(row    , col + 1); // right    
   } // end method markBlob

} // end class GridND2


Sample Output from Newer Version:

Input percentage probability (0 to 100): 50

XXX-----X---XXXX-X--        1   4   5   0   0   0   0   0  10   0   0   0  21  23  24  25   0 113   0   0
XX-X-XXXX-X-X--XXXX-        2   3   0  20   0  14  13  12  11   0 115   0  22   0   0  26 111 112 114   0
-X-XXX---X---X-X----        0   6   0  19  16  15   0   0   0 116   0   0   0 117   0  27   0   0   0   0
-X-XX-XXX-XXXX-XXX-X        0   7   0  18  17   0  56  55  57   0 121 120 119 118   0  28 100 101   0 122
XX---X-X-X-----X-XX-        9   8   0   0   0 123   0  54   0 124   0   0   0   0   0  29   0 102 110   0
---X--XXX-XXXXXX-X-X        0   0   0 125   0   0  62  53  52   0  44  43  39  38  31  30   0 103   0 126
-XX-XXXXXXXXX-X-XX--        0  73  74   0  64  63  61  58  51  50  45  42  40   0  32   0 109 104   0   0
XX--X-XX--X-X-XX-X--       75  72   0   0  65   0  60  59   0   0  46   0  41   0  33  37   0 105   0   0
-XXXXX--XXX--XXX-XX-        0  71  70  67  66  99   0   0  49  48  47   0   0  35  34  36   0 106 108   0
X-XX--XX---XX----X-X      127   0  69  68   0   0  91  92   0   0   0 128 141   0   0   0   0 107   0 142
-XX--XXXX--X-XX----X        0  98  76   0   0  89  90  93  97   0   0 129   0 146 147   0   0   0   0 143
--XXXXXX-XXXX-XX-X-X        0   0  77  78  87  88  95  94   0 134 131 130 138   0 148 149   0 150   0 144
X--X--X-XXX-XX---X-X      152   0   0  79   0   0  96   0 137 133 132   0 139 140   0   0   0 151   0 145
---XXX---X-X----X-X-        0   0   0  80  83  84   0   0   0 135   0 153   0   0   0   0 204   0 205   0
XX-XXX-X-X-X-XXX-X--      206 209   0  81  82  85   0 183   0 136   0 154   0 172 171 170   0 210   0   0
X---X--XX-XX-X-XX-XX      207   0   0   0  86   0   0 182 181   0 156 155   0 173   0 169 174   0 211 212
X-XX-XXXXXX----X-X-X      208   0 200 199   0 203 185 184 180 179 157   0   0   0   0 168   0 218   0 213
--XX--X--XX---XXX--X        0   0 201 198   0   0 186   0   0 178 158   0   0   0 166 167 176   0   0 214
X--XXXXX--XXXXXX--XX      219   0   0 197 194 193 187 190   0   0 159 160 163 164 165 175   0   0 217 215
--XXX-XXXX-XX-X-XX-X        0   0 202 196 195   0 188 189 191 192   0 161 162   0 177   0 220 221   0 216

  1  1  1  .  .  .  .  .  2  .  .  .  3  3  3  3  .  3  .  .
  1  1  .  2  .  2  2  2  2  .  4  .  3  .  .  3  3  3  3  .
  .  1  .  2  2  2  .  .  .  5  .  .  .  6  .  3  .  .  .  .
  .  1  .  2  2  .  3  3  3  .  6  6  6  6  .  3  3  3  .  7
  1  1  .  .  .  8  .  3  .  9  .  .  .  .  .  3  .  3  3  .
  .  .  . 10  .  .  3  3  3  .  3  3  3  3  3  3  .  3  . 11
  .  3  3  .  3  3  3  3  3  3  3  3  3  .  3  .  3  3  .  .
  3  3  .  .  3  .  3  3  .  .  3  .  3  .  3  3  .  3  .  .
  .  3  3  3  3  3  .  .  3  3  3  .  .  3  3  3  .  3  3  .
 12  .  3  3  .  .  3  3  .  .  . 13 13  .  .  .  .  3  . 14
  .  3  3  .  .  3  3  3  3  .  . 13  . 15 15  .  .  .  . 14
  .  .  3  3  3  3  3  3  . 13 13 13 13  . 15 15  . 16  . 14
 17  .  .  3  .  .  3  . 13 13 13  . 13 13  .  .  . 16  . 14
  .  .  .  3  3  3  .  .  . 13  . 18  .  .  .  . 19  . 20  .
 21 21  .  3  3  3  . 18  . 13  . 18  . 18 18 18  . 22  .  .
 21  .  .  .  3  .  . 18 18  . 18 18  . 18  . 18 18  . 23 23
 21  . 18 18  . 18 18 18 18 18 18  .  .  .  . 18  . 24  . 23
  .  . 18 18  .  . 18  .  . 18 18  .  .  . 18 18 18  .  . 23
 25  .  . 18 18 18 18 18  .  . 18 18 18 18 18 18  .  . 23 23
  .  . 18 18 18  . 18 18 18 18  . 18 18  . 18  . 26 26  . 23

There are 26 blobs.



Earlier version:

Here is a typical run:

Input percentage probability (0 to 100): 50

X-XX-X---XXXXXXXXX-X        1   0  77  78   0  80   0   0   0  44  45  48  49  52  53  56  57  75   0  81
X--X--X-XXXXXXXXX-X-        2   0   0  79   0   0  82   0  42  43  46  47  50  51  54  55  58   0  73   0
XXX---X-X--X---XXXXX        3   6   7   0   0   0  83   0  41   0   0  76   0   0   0  65  59  71  72  74
X-X-XX-XX----XXXX---        4   0   8   0  16  15   0  39  40   0   0   0   0  69  66  64  60   0   0   0
X-X--X-X-X---XXXXX-X        5   0   9   0   0  14   0  38   0  84   0   0   0  68  67  63  61  70   0  85
--XXXXXX--X-X---X--X        0   0  10  11  12  13  17  37   0   0  87   0  90   0   0   0  62   0   0  86
------X--XX---X---X-        0   0   0   0   0   0  18   0   0  89  88   0   0   0  91   0   0   0  92   0
-XX-XXX-----X---XX--        0  36  35   0  24  23  19   0   0   0   0   0  93   0   0   0  94  95   0   0
--XXX-XX-X-X-XXX-XXX        0   0  34  33  25   0  20  22   0  99   0 101   0 108 109 121   0  96  97  98
-X--X-X--X-X-XXXX---        0 123   0   0  26   0  21   0   0 100   0 102   0 107 110 120 119   0   0   0
---XX---X--XXXX-X--X        0   0   0  28  27   0   0   0 124   0   0 103 104 106 111   0 118   0   0 125
-XXX-XX--XX-X-XXX---        0  32  31  29   0 126 127   0   0 134 135   0 105   0 112 116 117   0   0   0
X--X--XXXXXX--XXX-XX      138   0   0  30   0   0 128 129 132 133 136 137   0   0 113 115 122   0 140 141
X------XX---X-X----X      139   0   0   0   0   0   0 130 131   0   0   0 143   0 114   0   0   0   0 142
--XX-X-----XXX-X----        0   0 172 173   0 174   0   0   0   0   0 147 144 150   0 155   0   0   0   0
X---X---X--XXXXXXXXX      175   0   0   0 179   0   0   0 180   0   0 146 145 149 151 154 156 157 170 171
X-X---XX-X-X--XX-X--      176   0 181   0   0   0 182 184   0 185   0 148   0   0 152 153   0 158   0   0
X--X--X-X--------X--      177   0   0 186   0   0 183   0 191   0   0   0   0   0   0   0   0 159   0   0
X--XXX----X---XXXXXX      178   0   0 187 188 190   0   0   0   0 192   0   0   0 166 164 163 160 168 169
----X-XXX-X-X--XXXX-        0   0   0   0 189   0 194 195 196   0 193   0 197   0   0 165 162 161 167   0


There are 35 blobs.

Code:

//----------------------------------------------------------------------
// BlobApp.java          by Dale/Joyce/Weems                   Chapter 4
//
// Instantiates a Grid based on a percentage probability provided by the
// user and reports the number of blobs in the Grid.
//----------------------------------------------------------------------
// Nick Duchon - modifications
// Date: Oct 5, 2008

import java.util.Scanner;

public class BlobAppND {
  static
  int [][] test = {{1,1,0,1},
                   {0,1,0,1},
                   {1,1,0,1},
                   {0,1,1,1}
                  }; // end test array
  public static void main(String[] args) {
    Scanner conIn = new Scanner(System.in);

    final int GRIDR = 20;   // number of grid rows
    final int GRIDC = 20;   // number of grid columns

    // Get percentage probability of blob characters
    int percentage;      
    System.out.print("Input percentage probability (0 to 100): ");
    if (conIn.hasNextInt())
      percentage = conIn.nextInt();
    else
    {
      System.out.println("Error: you must enter an integer.");
      System.out.println("Terminating program.");
      return;
    }
    System.out.println();

    // create grid
    GridND grid = new GridND(GRIDR, GRIDC, percentage);
//     Grid grid = new Grid(test);
   
    // display grid and blob count
    int c = grid.blobCount();
    System.out.println(grid);
    System.out.println("\nThere are " + c + " blobs.\n");
  } // end main
} // end class BlobAppND



//----------------------------------------------------------------------
// Grid.java              by Dale/Joyce/Weems                  Chapter 4
//
// Supports grid objects consisting of blob and non-blob characters.
// Allows the number of blobs it contains to be counted.
//----------------------------------------------------------------------

import java.util.Random;

public class GridND {
  protected int rows;         // number of grid rows
  protected int cols;         // number of grid columns
   
  protected boolean [][] grid;     // the grid containing blobs
  int [][] visited;            // used by blobCount
  int index = 1;
 
  public GridND (int [][] g) {
    rows = g.length;
    cols = g[0].length;
    grid = new boolean [rows][cols];
    visited = new int [rows][cols];  // true if location visited

    for (int r = 0; r < g.length; r++)
      for (int c = 0; c < g[r].length; c++)
        grid [r][c] = (g[r][c] == 1)?true:false;
  } // end 2-d int constructor

  public GridND (int rows, int cols, int percentage)
  // Preconditions: rows and cols > 0
  //                0 <= percentage <= 100
  //
  // Instantiates a grid of size rows by cols, where locations are set to
  // indicate blob characters based on the percentage probability.
  {
    this.rows = rows;
    this.cols = cols;
    grid = new boolean [rows][cols];
    visited = new int [rows][cols];  // true if location visited

    // to generate random numbers
    int randInt;
    Random rand = new Random();

    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
      {
        randInt = rand.nextInt(100);  // random number 0 .. 99
        if (randInt < percentage)
          grid[i][j] = true;
        else
          grid[i][j] = false;
      }
  } // end int int int constructor

  public String toString() {
    String gridString = "";
    for (int i = 0; i < rows; i++)
    {
      for (int j = 0; j < cols; j++)
      {
        if (grid[i][j])
          gridString = gridString + "X";
        else
          gridString = gridString + "-";
       }
       gridString += "     ";
       for (int j = 0; j < cols; j++) {
         gridString += String.format ("%4d", visited[i][j]);
       } // end for each row in the visited matrix also
      gridString = gridString + "\n";   // end of row
    } 
    return gridString;
  } // end toString method

  public int blobCount()
  // returns the number of blobs in this grid
  {
    int count = 0;
   
    // initialize visited
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        visited[i][j] = 0;
     
    // count blobs
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        if (grid[i][j] && visited[i][j] == 0)
        {
          count++;
          markBlob(i, j);
        }
      
  return count;
  } // end blobCount method
 
  private void markBlob(int row, int col)
  // Mark position row, col as having been visited.
  // Check and if appropriate mark locations above, below, left,
  // and right of that position.
  {
    visited[row][col] = index++;
  
    // check above
    if ((row - 1) >= 0)           // if its on the grid
      if (grid[row - 1][col])       // and has a blob character
        if (visited[row - 1][col] == 0)   // and has not been visited
          markBlob(row - 1, col);       // then mark it
   
    // check below
    if ((row + 1) < rows)        // if its on the grid
      if (grid[row + 1][col])       // and has a blob character
        if (visited[row + 1][col] == 0)   // and has not been visited
          markBlob(row + 1, col);       // then mark it
   
    // check left
    if ((col - 1) >= 0)           // if its on the grid
      if (grid[row][col - 1])       // and has a blob character
        if (visited[row][col - 1] == 0)   // and has not been visited
          markBlob(row, col - 1);       // then mark it
   
    // check right
    if ((col + 1) < cols)        // if its on the grid
      if (grid[row][col + 1])       // and has a blob character
        if (visited[row][col + 1] == 0)   // and has not been visited
          markBlob(row, col + 1);       // then mark it
  } // end method markBlob
}
// end class GridND
  

More Features - GridND5:

The yellow code is the code searching the 2D array of True/False cells.

blobCount goes through the array, looking in each row for a cell that is True and has not been visited yet, ie, is not part of a previously found blob.
Upon finding such a cell, this method starts a new Blob, then calls markBlob, starting at the found cell.

markBlob is a recursive method that starts at the cell passed as a parameter and:

// File: GridND5.java
// Date: Mar 18, 2017, Feb 15, 2019
// Author: Nicholas Duchon
// Based on Dale/Joyce/Weems Chapter 4, BlobApp.java and Grid.java

//----------------------------------------------------------------------
// BlobApp.java          by Dale/Joyce/Weems                   Chapter 4
//
// Instantiates a Grid based on a percentage probability provided by the
// user and reports the number of blobs in the Grid.
//----------------------------------------------------------------------
// Nick Duchon - modifications
// Date: Oct 5, 2008
//----------------------------------------------------------------------
// Grid.java              by Dale/Joyce/Weems                  Chapter 4
//
// Supports grid objects consisting of blob and non-blob characters.
// Allows the number of blobs it contains to be counted.
//
// Modifications by Nicholas Duchon
//----------------------------------------------------------------------

// Notes:
// Feb 16, 2019 - added GUI interface
// Nov 15, 2020 - more than one run at a time

import java.util.Scanner;
import java.util.Random;
import java.util.ArrayList;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JButton;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;

import java.awt.BorderLayout;
import java.awt.GridLayout;

import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;


class PairND5 { 
   int r, c;
   int index;
   int blob;

   PairND5 (int a, int b, int i, int s) {
      r = a; c = b;
      index = i;
      blob = s;
   }
  
   public String toString () {
      return String.format ("%3d %2d %2d", index, r, c);
   }
} // end class PairND5

class BlobND5 {
   ArrayList <PairND5> set = new ArrayList <> ();
   int group;

   public BlobND5 (int g) {group = g;}

   void add (int r, int c, int ix, int ib) {
      set.add (new PairND5 (r, c, ix, ib));
   } // end method add int int int

   public String toString () {
      String st = String.format ("\n%5d = ", group);
      int cnt = 0;
      for (PairND5 p: set) {
         st += p + " : ";
         if (++cnt % 10 == 0) st += String.format ("\n%8s", "");
      } // end for each cell in blob
      int ix = st.lastIndexOf (" : ");
      st = st.substring (0, ix);
      return st;
   } // end method toString
} // end class BlobND

public class GridND5 {
   static final int GRIDR = 30;   // number of grid rows
   static final int GRIDC = 20;   // number of grid columns
   static int [] OFFSETS = {1, 0, -1, 0, 0, 1, 0, -1}; // directions: right left down up
   static final String prompt =
      "Input percentage probability (0 to 100): "
      + "\nOptionally rows and columns:";
  
   int rows; // number of grid rows
   int cols; // number of grid columns
   int percentage; // percent of grid marked true
    
   boolean [][] grid;     // the grid containing blobs
   int     [][] visited;  // used by blobCount
   int     [][] id;       // the id of each blob - most useful in blob grid display
   int index = 1;         // number the order of visits to active cells
   int count = 0;         // number of the blob
   int [] off = OFFSETS.clone(); // default directions: down up right left
   ArrayList <BlobND5> blobs    = new ArrayList <> (); // useful in blob listing display
   ArrayList <PairND5> sequence = new ArrayList <> (); // useful in stepping
   BlobND5 bnd;
  
   public static void main(String[] args) {
      start ();
   } // end main method
  
   public static void start () {
      // Get percentage probability of blob characters
      int r = GRIDR, c = GRIDC;
      int percentage;
      while (true) {
         String name = javax.swing.JOptionPane.showInputDialog(
                null, prompt);
         if (name == null) return;
         Scanner s = new Scanner (name);
         if (s.hasNextInt()) {
            percentage = s.nextInt();
            if (percentage > 0 && percentage <= 100) {
               if (s.hasNextInt ()) r = s.nextInt();
               if (s.hasNextInt ()) c = s.nextInt();
               break;
            } // end if percentage within range
         } // end if first parameter is an int
      } // end geting input from the user
     
      // create grid
      GridND5 grid = new GridND5 (r, c, percentage);
      new GridGUIND5 (grid); // show GUI
   } // end static method start

   public GridND5 (int prows, int pcols, int p_percentage) {
      rows    = prows;
      cols    = pcols;
      grid    = new boolean [rows][cols]; // true means cell part of a blob
      visited = new int     [rows][cols]; // > 0 if location visited
      id      = new int     [rows][cols]; // which blob?
      percentage = p_percentage;
  
      // to generate random numbers
      Random rand = new Random();
  
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            grid [i][j] = (percentage > rand.nextInt(100));
      blobCount();
   } // end int/int/int constructor

   public String toString() {
      String gridString = "";
      gridString += "There are " + count + " blobs.";
     
      gridString += "\n\nGrid: <X=true | -=false> <visit number>\n";
      for (int i = 0; i < rows; i++) {
         for (boolean b: grid[i])
            gridString += b?"X":"-";
         gridString += "     ";
         for (int m: visited[i]) {
            gridString += String.format ("%4d", m);
         } // end for each row in the visited matrix also
         gridString = gridString + "\n";   // end of row
      } // end for each row of the grid
     
      gridString += "\nGrid: <.|blob number>";
      for (int [] r: id) {
         gridString += "\n";
         int cnt = 0;
         for (int v: r) {
            gridString += (v==0)?"  .":String.format ("%3d", v);
         } // end for each cell
      } // end for each row

//       gridString += "\n\n<blob number> = [<visit number> <blob number> <row> <column>]+";
      gridString += "\n\n<blob number> = [<visit number> <row> <column> : ]+";
      for (BlobND5 b: blobs)
         gridString += b;

      return gridString;
   } // end method toString
  
   public void blobCount (int [] po) {
      off = po;
      blobCount();
   }

    // counts number of blobs in this grid
   public void blobCount() {
      // initialize visited and id arrays
      count = 0;
      index = 1;
      sequence.clear();
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++) {
            visited [i][j] = 0;
            id      [i][j] = 0;
         } // init visited and id arrays
       
      // count blobs
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            if (grid[i][j] && visited[i][j] == 0) {
               count++;
               bnd = new BlobND5 (count);
               blobs.add (bnd);
               markBlob(i, j);
               sequence.addAll (bnd.set);
            } // end for each unvisited blob cell

   } // end method blobCount
  
    // Mark position row, col as having been visited.
    // Check and if appropriate mark locations above, below, left,
    // and right of that position.
   private void markBlob(int row, int col) {
      if (row <  0   ) return; // these are out of grid locations
      if (row >= rows) return;
      if (col <  0   ) return;
      if (col >= cols) return;
     
      if (!  grid [row][col]     ) return; // cell not in any blob
      if (visited [row][col] != 0) return; // cell already visited
     
      // add this cell the current blob
      bnd.add (row, col, index, count);
      visited [row][col] = index++;
      id      [row][col] = count;
     
      // default: down up right left
      markBlob (row + off[0], col + off[1]); // first direction
      markBlob (row + off[2], col + off[3]); // second direction
      markBlob (row + off[4], col + off[5]); // third direction
      markBlob (row + off[6], col + off[7]); // fourth direction
   } // end method markBlob

} // end class GridND2

class GridGUIND5 extends JFrame {
   public static final long serialVersionUID = 1; // ND: junk
  
   static int windowCount = 0;
   static String name = "Grid GUI ND 5";
  
   // Some nice contrasting colors, show black text nicely as well
   java.awt.Color [] colors = {
      new java.awt.Color(100, 100, 255),
      java.awt.Color.getHSBColor (.10f, 1f, 1f),
      java.awt.Color.getHSBColor (.20f, 1f, 1f),
      java.awt.Color.getHSBColor (.30f, 1f, 1f),
      java.awt.Color.getHSBColor (.40f, 1f, 1f),
      java.awt.Color.getHSBColor (.50f, 1f, 1f),
      java.awt.Color.getHSBColor (.60f, .5f, 1f),
      java.awt.Color.getHSBColor (.70f, .5f, 1f),
      java.awt.Color.getHSBColor (.80f, 1f, 1f),
      java.awt.Color.getHSBColor (.90f, 1f, 1f),
      java.awt.Color.getHSBColor (.15f, 1f, 1f),
      java.awt.Color.getHSBColor (.25f, 1f, 1f),
      java.awt.Color.getHSBColor (.35f, 1f, 1f),
      java.awt.Color.getHSBColor (.45f, 1f, 1f),
      java.awt.Color.getHSBColor (.55f, 1f, 1f),
      java.awt.Color.getHSBColor (.65f, .5f, 1f),
      java.awt.Color.getHSBColor (.75f, .5f, 1f),
      java.awt.Color.getHSBColor (.85f, 1f, 1f),
      java.awt.Color.getHSBColor (.95f, 1f, 1f),
      java.awt.Color.getHSBColor (.13f, 1f, 1f),
      java.awt.Color.cyan,
      java.awt.Color.green,
      java.awt.Color.magenta,
      java.awt.Color.orange,
      java.awt.Color.pink,
      java.awt.Color.red,
      java.awt.Color.yellow
   };
  
   JButton buttons [][];
   GridND5 g;
   int step = 0;
  
   public GridGUIND5 (GridND5 gp) {
      // make sure button colors work correctly on this O/S:
      try {
         javax.swing.UIManager.setLookAndFeel(
         javax.swing.UIManager.getCrossPlatformLookAndFeelClassName() );
      } catch (Exception e) {
         e.printStackTrace();
      }
     
      g = gp;

      windowCount ++;
    
      addWindowListener (
         new WindowAdapter () {
            public void windowClosing (WindowEvent e) {
               windowCount --;
               if (windowCount == 0) System.exit (0);
            } // end closing event handler method
         } // end new inner adapter
      ); // end adding method     

      JPanel  jpb = new JPanel (); // control buttons
      JButton jba = new JButton ("Show visits"); // show visits count
      JButton jbb = new JButton ("Show blobs");  // show blobs count
      JButton jbf = new JButton ("Step up");     // step forward
      JButton jbr = new JButton ("Step back");   // step reverse
      JButton jbz = new JButton ("Step zero");   // step reset
      JButton jbo = new JButton ("Probe Order"); // set order of visits
      JButton jbn = new JButton ("New grid");    // new grid
     
      jpb.add (jba); jpb.add (jbb); jpb.add (jbf);
      jpb.add (jbr); jpb.add (jbz); jpb.add (jbo);
      jpb.add (jbn);
     
      jpb.setLayout (new GridLayout (0,1));
      JPanel jpbA = new JPanel ();
      jpbA.add (jpb);
      add (jpbA, BorderLayout.WEST);
     
      jba.addActionListener (e -> showVisits ());
      jbb.addActionListener (e -> showBlobs  ());
      jbf.addActionListener (e -> stepUp     ());
      jbr.addActionListener (e -> stepDown   ());
      jbz.addActionListener (e -> stepZero   ());
      jbo.addActionListener (e -> setOrder   ());
      jbn.addActionListener (e -> GridND5.start());
     
      JPanel jp = new JPanel ();
      jp.setLayout (new GridLayout (g.rows, g.cols));
      buttons = new JButton [g.rows][g.cols];
      for (int i = 0; i < g.rows; i++)
         for (int j = 0; j < g.cols; j++) {
            jp.add (buttons [i][j] = new JButton (""));
            if (g.id[i][j] > 0)
               buttons [i][j].setBackground (
                  colors[g.id[i][j]%colors.length]);
         } // end for each button
      showVisits ();
        
      String title = String.format ("%s: %d%%, %d x %d, Order: DURL", name, g.percentage, g.rows, g.cols);
      setTitle (title);
      add (jp, BorderLayout.CENTER);
      pack ();
      setLocationRelativeTo (null);
      setVisible (true);

      // Text display frame:
      JFrame jf = new JFrame ();
      title = String.format ("%s text: %d%%, %d x %d", name, g.percentage, g.rows, g.cols);
      jf.setTitle (title);
      jf.setSize (400, 200);
      JTextArea jta = new JTextArea ();
      JScrollPane jsp = new JScrollPane (jta);
      jta.setFont (new java.awt.Font ("Monospaced", java.awt.Font.PLAIN, 12));
      jta.setText (g.toString());
      jta.setCaretPosition (0);
      jf.add (jsp, BorderLayout.CENTER);
      jf.setLocation (10, 10);
      jf.setVisible (true);
     
      toFront();
   } // end BlobND5 constructor
  
   void setOrder () {
      String prompt = "select order, eg: LRUD\nfor left right up down";
      int [] offsets = g.OFFSETS.clone();
      String orderString = "DURL";
      String selection = null;
      while (true) {
         selection = javax.swing.JOptionPane.showInputDialog(
                null, prompt);
         if (selection == null) return;
         char [] order = selection.toUpperCase().toCharArray();
         if (order.length != 4) continue;
         int found = 0;
         for (int i = 0; i < 4; i++)
            switch (order[i]) {
               case  'L': found+=1; offsets[2*i]= 0; offsets[2*i+1]=-1; break;
               case  'R': found+=2; offsets[2*i]= 0; offsets[2*i+1]= 1; break;
               case  'U': found+=4; offsets[2*i]=-1; offsets[2*i+1]= 0; break;
               case  'D': found+=8; offsets[2*i]= 1; offsets[2*i+1]= 0; break;
            } // end switch
         if (found == 15) break; // one of each letter
      } // end geting input from the user
      g.blobCount (offsets);
      orderString = selection.toUpperCase();
      String title = String.format (
         "%s: %d%%, %d x %d, Order: %s",
         name, g.percentage, g.rows, g.cols, orderString);
      setTitle (title);
      step = 0;
      showVisits ();
   } // end method setOrder
  
   void stepUp () {
      step++;
      if (step > g.sequence.size())
         step = g.sequence.size();
      showVisits (step);
   } // end method stepUp
  
   void stepDown () {
      --step;
      if (step < 0) step = 0;
      showVisits (step);
   } // end method stepDown
  
   void stepZero () {
      step = 0;
      showVisits (step);
   } // end method stepDown
  
   void showBlobs () {
      for (int i = 0; i < g.sequence.size(); i++) {
         int r = g.sequence.get(i).r;
         int c = g.sequence.get(i).c;
         int v = g.sequence.get(i).blob;
         buttons[r][c].setText ("" + v);
      } // end for all cells
   } // end method showBlobs
  
   void showVisits (int number) {
      for (int i = 0; i < number; i++) {
         int r = g.sequence.get(i).r;
         int c = g.sequence.get(i).c;
         int v = g.sequence.get(i).index;
         buttons[r][c].setText ("" + v);
      } // number of pairs to show
      for (int i = number; i < g.sequence.size(); i++) {
         int r = g.sequence.get(i).r;
         int c = g.sequence.get(i).c;
         buttons[r][c].setText ("");
      } // end for rest of cells
   } // end method showVisits int
  
   void showVisits () {
      showVisits (g.sequence.size());
   } // end method showBlobs

} // end class GridGUIND5


ND.