EDIT: Ok, here is a solution that will work for complex shapes
public class BlockCounter {
public static void main(String[] args) {
Board board = null;
try {
board = new Board("in3.txt");
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
System.out.println("Block count: " + board.getBlockCount());
}
}
class Board {
ArrayList<String> data = new ArrayList<>();
boolean[][] used;
int colCount = 0;
public Board(String filename) throws FileNotFoundException, IOException {
try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
String line;
while ((line = br.readLine()) != null) {
data.add(line);
colCount = Math.max(colCount, line.length());
}
}
}
public int getBlockCount() {
used = new boolean[data.size()][colCount];
int count = 0;
for (int row = 0; row < data.size(); row++)
for (int col = 0; col < colCount; col++)
used[row][col] = peek(row, col) == '1';
for (int row = 0; row < data.size(); row++)
for (int col = 0; col < colCount; col++)
if (used[row][col]) {
fill(row, col);
count++;
}
used = null;
return count;
}
public char peek(int row, int col) {
if (row < 0 || row >= data.size() || col < 0)
return '0';
String rowData = data.get(row);
if (col >= rowData.length())
return '0';
return rowData.charAt(col);
}
public void fill(int row, int col) {
if (used[row][col]) {
used[row][col] = false;
if (row > 0 && used[row - 1][col])
fill(row - 1, col);
if (col > 0 && used[row][col - 1])
fill(row, col - 1);
if (col < colCount - 1 && used[row][col + 1])
fill(row, col + 1);
if (row < data.size() - 1 && used[row + 1][col])
fill(row + 1, col);
}
}
public int getRowCount() {
return data.size();
}
public int getColCount() {
return colCount;
}
}
Explanation:
When Board.getBlockCount() is called if creates a temporary array of booleans to work with so the original board is not messed up. Then it searches the entire board for "trues" (which correspond to '1's on the board). Every time a "true" is found, a flood fill algorithm clears the entire shape to which it is connected.
If you need more performance and less memory usage (specially stack) for larger boards, you can use another flood fill algorithm like in the example that follows. The big advantage here is that it doesn't use the stack for every pixel like the one above. It is considerably more complex though.
public class BlockCounter2 {
public static void main(String[] args) {
Board2 board = null;
try {
board = new Board2("in4.txt");
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
System.out.println("Block count: " + board.getBlockCount());
}
}
class Board2 {
ArrayList<String> data = new ArrayList<>();
boolean[][] used;
Deque<Point> pointStack = new LinkedList<>();
int colCount = 0;
public Board2(String filename) throws FileNotFoundException, IOException {
try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
String line;
while ((line = br.readLine()) != null) {
data.add(line);
colCount = Math.max(colCount, line.length());
}
}
}
public int getBlockCount() {
used = new boolean[data.size()][colCount];
int count = 0;
for (int row = 0; row < data.size(); row++)
for (int col = 0; col < colCount; col++)
used[row][col] = peek(row, col) == '1';
for (int row = 0; row < data.size(); row++)
for (int col = 0; col < colCount; col++)
if (used[row][col]) {
fill(row, col);
count++;
}
used = null;
return count;
}
public char peek(int row, int col) {
if (row < 0 || row >= data.size() || col < 0)
return '0';
String rowData = data.get(row);
if (col >= rowData.length())
return '0';
return rowData.charAt(col);
}
public void fill(int row, int col) {
pointStack.push(new Point(col, row));
Point p;
while (pointStack.size() > 0) {
p = pointStack.pop();
fillRow(p.y, p.x);
}
}
private void checkRow(int row, int col, int minCol, int maxCol) {
boolean uu = false;
for (int x = col; x < maxCol; x++) {
if (!uu && used[row][x])
pointStack.add(new Point(x, row));
uu = used[row][x];
}
uu = true;
for (int x = col; x > minCol; x--) {
if (!uu && used[row][x])
pointStack.add(new Point(x, row));
uu = used[row][x];
}
}
private void fillRow(int row, int col) {
int lx, rx;
if (used[row][col]) {
for (rx = col; rx < colCount; rx++)
if (used[row][rx])
used[row][rx] = false;
else
break;
for (lx = col - 1; lx >= 0; lx--)
if (used[row][lx])
used[row][lx] = false;
else
break;
if (row > 0)
checkRow(row - 1, col, lx, rx);
if (row < data.size() - 1)
checkRow(row + 1, col, lx, rx);
}
}
public int getRowCount() {
return data.size();
}
public int getColCount() {
return colCount;
}
}
EDIT2: Both solutions were made using input from txt files in order to make the debugging and testing easier for larger arrays. If you need them to work with user input (the same you have in your code) as well, just make the following changes:
Change the main method so it will listen from user input (again):
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int rowNum=sc.nextInt();
int columnNum=sc.nextInt(); // Note columnNum is not necessary
String[] matrix = new String[rowNum]; // I hope char[][] is not a requirement
for (int a = 0; a < rowNum; a++) // Read array data from user input
matrix[a] = sc.next();
sc.close();
Board2 board = new Board2(matrix); // Call the new constructor
System.out.println("Block count: " + board.getBlockCount());
}
Add a new constructor to Board2, that takes a String[] as input:
public Board2(String[] data) {
for (String line : data) {
this.data.add(line);
colCount = Math.max(colCount, line.length());
}
}
You may remove the previous constructor Board2(String filename) if it is not useful for you but it's not necessary.
