Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 155

Presumably, we will need a variable that keeps count of the number of organisms. Let's call it orgCount . When a 1
is encountered for the first time, we will change it to orgCount + 1 . Thus, the cells of organism 1 will be labeled 2 , the
cells of organism 2 will be labeled 3 , and so on.
This is necessary since, if we start labeling from 1, we would not be able to distinguish between a 1 representing a
not-yet-met cell and a 1 indicating a cell belonging to organism 1.
This “adding 1 to the label” is necessary only while we are processing the grid . When we print it, we will subtract 1
from the label so that, on output, organism 1 will be labeled 1 , organism 2 will be labeled 2 , and so on.
In writing the program, we assume that the grid data is stored in an array G and consists of m rows and n columns.
We will use MaxRow and MaxCol to denote maximum values for m and n , respectively. Data for the program consists of
values for m and n , followed by the cell data in row order. For example, data for the previous grid will be supplied as
follows:
5 7
0 1 0 1 1 1 0
0 0 1 1 0 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 1
1 1 0 0 0 1 0
We assume that the data will be read from a file, orgs.in , and output will be sent to the file orgs.out .
The gist of the program logic is as follows:
scan the grid from left to right, top to bottom
when we meet a 1, we have a new organism
add 1 to orgCount
call a function findOrg to mark all the cells of the organism
The function findOrg will implement the four possibilities outlined earlier. When it sees a 1 in grid position ( i, j ),
say, it will call itself recursively for each of the grid positions to the north, east, south, and west of ( i, j ). All the details
are shown in Program P5.2.
Program P5.2
import java.io.*;
import java.util.*;
public class Organisms {
static int orgCount = 0;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("orgs.in"));
PrintWriter out = new PrintWriter(new FileWriter("orgs.out"));
int m = in.nextInt(), n = in.nextInt();
int[][] G = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
G[i][j] = in.nextInt();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (G[i][j] == 1) {
orgCount++;
findOrg(G, i, j, m, n);
}