Extra Credit Program: Recursion, Find Groups

This is a modification of problem 7.46 from the textbook. Use Cartesian coordinates (column, row) to refer to squares: (0,0) is the upper, left-hand corner of the board, (2,1) would be two squares to the right and one down from that.

The FindGroup class must provide these methods:

• public FindGroup(boolean[][] board) Constructor to initialize to a given board. The board is guaranteed to be rectangular. A value of true indicates that the corresponding square is occupied.
• public FindGroup(String board) Similar to above, but the board is defined by the given string parameter. The string consists of substrings of "_" (underbar) and "X" characters, each substring separated by a newline ('\n') character. The substrings will all be of the same length. The "X" characters correspond to the occupied cells of a grid, while the "_" correspond to unoccupied cells.
• public void printBoard() Print the board represented by the FindGroup object. The first line should act like a "header line", enumerating the columns that will be aligned in subsequent lines. Each following line will be the representation of one row of the board, prefaced with the index of that row. Each row will consist of a '_' character for each non-occupied cell, and a 'X' for each occupied cell. Here's a sample:

     01234567890
  0: ___XXXX__X_
  1: ______X__X_
  2: _XXXXXX__X_
  3: ________XXX
  4: ______XXX__
    

• public int sizeGroup(int col, int row); Return the size of the group containing the given square. If square is not occupied, return 0.
• public int numGroups( ) Return the number of groups in the board. Could be 0.
• public void printGroups() Print all groups in the boards. Make sure no square appears in more than one group. Output should be of the form shown below:

  Group 1: {(3,8), (4,8)}
  Group 2: {(9,9), (9,8)}
  

  List the groups that appear from top to bottom. Each group should appear on its own line of output. If more than one group's topmost element appears in the same row, print the leftmost group first, then the next to the right, etc.

Testing Your Code

I will test your code using, at least, the driver Main.java. Keep in mind that I may test your code using other strings and boolean arrays. You shouldn't assume anything about the dimensions of the arrays except that they are guaranteed to be 2-d and rectangular.

Here is the output I generated when running Main.java using my implementation of FindGroup:

   0123456789
0: XX_X______
1: _X_X______
2: _XXX______
3: __________
4: __________
5: _____XX___
6: ______X___
7: ______XX_X
8: ________XX
9: ________XX
Group 1: ((0,0) (1,0) (1,1) (1,2) (2,2) (3,2) (3,1) (3,0) )
Group 2: ((5,5) (6,5) (6,6) (6,7) (7,7) )
Group 3: ((9,7) (9,8) (9,9) (8,9) (8,8) )
Number of groups is: 3 and size of group at 3,0 is 8
   01234567890
0: ___XXXX__X_
1: ______X__X_
2: _XXXXXX__X_
3: ________XXX
4: ______XXX__
Group 1: ((3,0) (4,0) (5,0) (6,0) (6,1) (6,2) (5,2) (4,2) (3,2) (2,2) (1,2) )
Group 2: ((9,0) (9,1) (9,2) (9,3) (10,3) (8,3) (8,4) (7,4) (6,4) )
Number of groups is: 2 and size of group at 3,0 is 11

Submission:

Submit a zip file containing your source code, as well as a text file containing a transcript of the execution of Main.java using your implementation.