There is a matrix of cells of a certain size. A cell has two states: busy and empty. It is necessary to count the number of groups of cells and the number of cells in each group. The group is considered to be adjacent cells, but not diagonally.

enter image description here

In Figure 4, groups: in the 1st group 6 cells, in the rest - one by one.

Tried to do the function first to check only one group. If a group is found, then we count the number of cells in it and for these cells we make a state β€” empty, so that at the next checkout this group no longer β€œinterferes”. The main problem arose, of course, in the condition of finding the group. I tried to do something like that, but then I realized that this is nonsense, plus we fall outside the bounds of the array. How can this check be implemented?

public int getNumberCells(final Cell cellOccupied) { int numberRows = field.getNumberRows(); int numberColumns = field.getNumberColumns(); int count = 0; for (int i = 0; i < numberRows; i++) { for (int j = 0; j < numberColumns; j++) { if (field.getCell(i, j) == field.getCell(i, j + 1) && field.getCell(i, j) == cellOccupied) { count++; } if (field.getCell(i, j) == field.getCell(i + 1, j) && field.getCell(i, j) == cellOccupied) { count++; } } } return count; }
  • such a task was remembered on it-planet And if by sabzh, something like this algorithm was born - find 1 cell shaded, take all those who can be with it in the same group (check above left below to the right) and do the same for these cells - Andrew Bystrov 1:28 pm
  • @AndrewBystrov, yes, that's right, but if you check each one, they will be repeated. Each cell can hang some boolean, such as this cell has already been tested or not, if checked, it is not necessary to count it, but how to hang it then ... - compl
  • yes, not a bad option - Andrew Bystrov
  • There is clearly asking for recursion. Check cell, find neighbors, check neighbors and so on. If you do not add a "already checked" marker, the algorithm will work, but there may be many unnecessary passes. - Sergey Snegirev pm

2 answers 2

To search for groups, use the classic fill algorithm.

 public class Test { static final int columns = 8; static final int rows = 3; static int[][] matrix = { { 0,0,1,1,1,0,1,0 }, { 0,1,1,0,0,0,0,1 }, { 0,1,0,0,0,0,1,0 } }; static int floodFill(int row, int col) { if (row < 0 || col < 0 || col >= columns || row >= rows) return 0; if (matrix[row][col] != 1) return 0; matrix[row][col] = 2; return 1 + floodFill(row + 1, col) + floodFill(row - 1, col) + floodFill(row, col + 1) + floodFill(row, col - 1); } public static void main(String []args) { int count = 0; for (int row = 0; row < rows; row++) { for (int col = 0; col < columns; col++) { if (matrix[row][col] == 1) { count++; System.out.println(floodFill(row, col)); } } } System.out.println(count); } }

Update : added counting the number of items in the group.

  • Damn, that's cool, thanks! I did not know about this algorithm. Just how now to find out the number of elements in each group? - compl
  • @compl Corrected the code. - Alexander Petrov

Single-pass algorithm without recursion:

We touch the elements from left to right and from top to bottom. Having met the value 1, we replace it, for example, with 11. Then, in the process of searching, having found the value 1, which borders on 11, we replace it by 11, and if it does not, then by 12, etc. As a result, we call each group its unique number. In parallel, in a separate array, we count how many times we changed 1 to the value of the named group. Most likely, conflicts will arise like the fact that different β€œnames” were assigned to the same group. It is necessary to simultaneously identify such conflicts. The conflict is resolved by maintaining the third array of "synonyms". If we have 1, which borders on, for example, 11 and 12, then we assume that 11 and 12 are the same group.

Code implementing algorithm:

 public class Test3 { public static void main(String[] args) { int[][] matrix = { { 0,1,1,0,1,0,0,1 }, { 0,0,1,1,1,1,0,1 }, { 1,1,0,1,0,0,1,1 }, { 1,0,1,0,1,1,0,1 } }; getMatrixGroupsFrom01( matrix ); } public static void getMatrixGroupsFrom01( int[][] matrix ) { int width = matrix[0].length; int height = matrix.length; int groupsCount = 10; // first group - 11, second - 12 ... int group1, group2; HashMap<Integer,Integer> groupsLength = new HashMap<Integer,Integer>(); HashMap<Integer,List<Integer>> synonims = new HashMap<Integer,List<Integer>>(); List<Integer> currentSyn; for ( int i = 0; i < width; i++ ) { for ( int j = 0; j < height; j++ ) { if ( matrix[j][i] == 1 ) { // Ссли тСкущая ячСйка ΠΏΡ€ΠΈΠ½Π°Π΄Π»Π΅ΠΆΠΈΡ‚ ΠΏΠΎΠΊΠ° нСизвСстной Π³Ρ€ΡƒΠΏΠΏΠ΅ group1 = group2 = 0; // сброс Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ if ( j>0 && matrix[j-1][i]>0 ) group1 = matrix[j-1][i]; // Π³Ρ€ΡƒΠΏΠΏΠ° свСрху if ( i>0 && matrix[j][i-1]>0 ) group2 = matrix[j][i-1]; // Π³Ρ€ΡƒΠΏΠΏΠ° снизу if ( group1 == 0 && group2 == 0 ) { // Ссли ΠΎΠΊΡ€ΡƒΠΆΠ°ΡŽΡ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½ΡƒΠ»ΠΈ, Ρ‚ΠΎ Π½Π°Π΄ΠΎ Π·Π°Π΄Π°Ρ‚ΡŒ Π½ΠΎΠ²ΡƒΡŽ Π³Ρ€ΡƒΠΏΠΏΡƒ groupsCount++; // Π½ΠΎΠ²ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π³Ρ€ΡƒΠΏΠΏΡ‹ matrix[j][i] = groupsCount; groupsLength.put( groupsCount, 1 ); } else if ( group1 == 0 || group2 == 0 || group1 == group2 ) { // Ссли Π³Ρ€ΡƒΠΏΠΏΡ‹ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ ΠΈΠ»ΠΈ ΠΎΠ΄Π½Π° ΠΈΠ· Π½ΠΈΡ… Ρ€Π°Π²Π½Π° 0 matrix[j][i] = group1 == 0 ? group2 : group1; groupsLength.put( matrix[j][i], groupsLength.get( matrix[j][i] )+1 ); // ΠΈΠ½ΠΊΡ€Π΅ΠΌΠ΅Π½Ρ‚ } else { // Ссли Π³Ρ€ΡƒΠΏΠΏΡ‹ Ρ€Π°Π·Π½Ρ‹Π΅, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΊΠΎΠ½Ρ„Π»ΠΈΠΊΡ‚. ΠšΠΎΠ½Ρ„Π»ΠΈΠΊΡ‚ Π½ΡƒΠΆΠ½ΠΎ Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΡ‚ΡŒ создав синоним if ( group1 > group2 ) { // Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ ΠΏΠΎΡ‚ΠΎΠΌ с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ int swap = group2; group2 = group1; group1 = swap; } //System.out.println( group1 + " " + group2 ); if ( synonims.containsKey( group1 ) ) { currentSyn = synonims.get( group1 ); } else { currentSyn = new ArrayList<Integer>(); } if ( currentSyn.indexOf( group2 ) == -1 ) { // Ссли Ρ‚Π°ΠΊΠΎΠ³ΠΎ синонима Π΅Ρ‰Π΅ Π½Π΅Ρ‚ currentSyn.add( group2 ); } synonims.put(group1, currentSyn); // создаСм синоним matrix[j][i] = group1; groupsLength.put( group1, groupsLength.get( group1 )+1 ); // ΠΈΠ½ΠΊΡ€Π΅ΠΌΠ΅Π½Ρ‚ } } System.out.print( matrix[j][i] + "\t" ); } System.out.print( "\n" ); } // с этого ΠΌΠΎΠΌΠ΅Π½Ρ‚Π° Π΅ΡΡ‚ΡŒ ΠΈΡΡ‡Π΅Ρ€ΠΏΡ‹Π²Π°ΡŽΡ‰ΠΈΠ΅ Π΄Π°Π½Π½Ρ‹Π΅ ΠΎ Π³Ρ€ΡƒΠΏΠΏΠ°Ρ… int synSize = synonims.size(); Integer[] s = {}; s = synonims.keySet().toArray( s ); for ( int i=0; i < synSize; i++ ) { // ΠΏΠ΅Ρ€Π΅Π±ΠΈΡ€Π°Π΅ΠΌ синонимы System.out.print( "\n" + s[i] + " => " ); List<Integer> sd = synonims.get( s[i] ); Iterator<Integer> cs = sd.iterator(); while ( cs.hasNext() ) { int synVal = cs.next(); System.out.print( synVal + " " ); groupsLength.put( s[i], groupsLength.get( s[i] ) + groupsLength.get( synVal ) ); // добавляСм ΠΊ основной суммС сумму синонима groupsLength.remove( synVal ); // удаляСм ΡΠΈΠ½ΠΎΠ½ΠΈΠΌΠΈΡ‡Π½ΡƒΡŽ сумму } } System.out.println( "\n" ); s = groupsLength.keySet().toArray( s ); for ( int i = 0; i < s.length; i++ ) { System.out.println( "Group:\t" + s[i] + "\tSize: " + groupsLength.get( s[i] ) ); } } }

Result of work:

 0 0 11 11 12 0 11 0 12 12 0 13 0 12 12 0 14 12 0 15 0 12 0 15 0 0 16 0 17 17 16 16 16 => 17 12 => 14 Group: 16 Size: 5 Group: 11 Size: 3 Group: 12 Size: 8 Group: 13 Size: 1 Group: 15 Size: 2

To bring beauty inside the matrix, we need another pass, in which synonyms are replaced by one value, but for the tasks posed in the question, beauty is not needed.