Write a recursive method that counts the number of creatures on a grid. A creatu
ID: 3760888 • Letter: W
Question
Write a recursive method that counts the number of creatures on a grid. A creature is defined as a contiguous collection of 1's (connected horizontally vertically and diagonally).
Input
Max dimensions of the array
Distribution of organisms on the array
Output
The number of creatures and the layout of the grid showing the locations of the creatures.
Requirements checklist:
Documented source code (include any assumptions you make)
Input File (in.txt)
The format of the input file is as follows: First line is the dimensions of the grid.. Then the grid containing 1s for the creatures and 0s for the spaces. The file terminates by 0 0.
5 5
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
5 5
0 0 0 0 0
0 1 1 1 0
0 0 0 0 1
1 1 1 0 0
0 0 0 0 0
0 0
Output File (out.txt)
Experiment # 1
Number of Creatures: 1
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 2 2 2 0
0 0 0 0 0
Experiment #2
Number of Creatures: 1
0 0 0 0 0
0 1 1 1 0
0 0 0 0 2
0 3 3 3 0
0 0 0 0 0
THE INPUT SHOULD BE READ FROM (.TXT)
Explanation / Answer
import java.io.*;
class Cell
{
public int value;
public int creature;
ArrayList<Cell> connections = new ArrayList<Cell>();
}
public class Creatures
{
public static void main(String[] args) throws IOException
{
FileInputStream in = new FileInputStream("in.txt");
BufferedReader br = new BufferedReader(new InputStreamReader(in));
PrintWriter pw = new PrintWriter("out.txt");
String line;
String[] split;
int x, y, experiment = 1;
try
{
while(true)
{
line = br.readLine();
split = line.split(" ");
x = Integer.parseInt(split[0]);
y = Integer.parseInt(split[1]);
if(x == 0 && y == 0) return; // end of file
int[][] values = new int[x][y];
br.readLine(); // skip empty line
for(int i = 0; i < x; i++)
{
line = br.readLine();
split = line.split(" ");
for(int j = 0; j < y; j++) values[i][j] = Integer.parseInt(split[j]);
br.readLine(); // skip empty line
}
findCreatures(x, y, values, experiment, pw);
experiment++;
}
}
catch(IOException e)
{
System.out.println(e);
return;
}
finally
{
br.close();
in.close();
pw.close();
}
}
static void findCreatures(int x, int y, int[][] values, int experiment, PrintWriter pw)
{
// create a 2D array of Cells corresponding to values array
Cell[][] cells = new Cell[x][y];
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
cells[i][j] = new Cell();
cells[i][j].value = values[i][j];
}
}
// get all connected cells
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
if (i > 0 && cells[i - 1][j].value == 1)
{
cells[i][j].connections.add(cells[i - 1][j]);
}
if (i < x - 1 && cells[i + 1][j].value == 1)
{
cells[i][j].connections.add(cells[i + 1][j]);
}
if (j > 0 && cells[i][j - 1].value == 1)
{
cells[i][j].connections.add(cells[i][j - 1]);
}
if (j < y - 1 && cells[i][j + 1].value == 1)
{
cells[i][j].connections.add(cells[i][j + 1]);
}
}
}
int creature = 1;
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
if (cells[i][j].value == 1 && cells[i][j].creature == 0)
{
cells[i][j].creature = creature;
addConnections(cells[i][j], creature);
creature++;
}
}
}
// print results to file
pw.println("Experiment#" + experiment);
pw.println();
pw.println("Number of Creatures: " + (creature - 1));
pw.println();
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
pw.print(cells[i][j].creature + " ");
}
pw.println();
pw.println();
}
pw.println();
}
static void addConnections(Cell cell, int creature)
{
int size = cell.connections.size();
if( size == 0) return;
for(int i = 0; i < size; i++)
{
Cell connected = cell.connections.get(i);
if (connected.creature == 0)
{
connected.creature = creature;
addConnections(connected, creature); // recursive call
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.