FANDOM


In our matrix problem, we don't yet have a nice graph representation. We could build a graph representation from a given matrix and then run the general CC algorithm on it, but it's much easier to directly hardcode the graph structure into the algorithm. That means, instead of having an explicit list of neighbours for each node, we look at the cells around a cell and view them as "neighbours" if they have the same colour. Furthermore, our "numberOfComponents" will have two nested loops to walk over all "nodes". Usually this algorithm is called something like "FloodFill", since we somehow "flood" or "fill" the regions.

This time the code is in Java. The matrix is given as an array of Strings "land". Height and width of the matrix are stored in "m" and "n", respectively.

  String[] land;
  int m, n;
  boolean[][] seen;
  
  void flood ( int i, int j, char farmer ) {
    if( i<0 || i>=m || j<0 || j>=n || seen[i][j] || land[i].charAt(j)!=farmer )
      return;
    seen[i][j] = true;
    flood( i-1, j, farmer );
    flood( i+1, j, farmer );
    flood( i, j-1, farmer );
    flood( i, j+1, farmer );
  }
  
  int numberOfRegions ( String[] land ) {
    this.land = land;
    m = land.length;
    n = land[0].length();
    seen = new boolean[m][n];
    
    int answer = 0;
    for( int i=0; i<m; ++i ){
      for( int j=0; j<n; ++j ){
	if( ! seen[i][j] ){
	  ++answer;
	  flood( i, j, land[i].charAt(j) );
	}
      }
    }
    
    return answer;
  }
     

We should only visit a neighbour cell if it has the same colour as the current cell. But checking this directly would require much code, since we also have to check if the coordinates of each neighbour are inside the matrix before looking at its colour. Instead, we defer this check and blindly visit all neighbour cells and we add the out-of-bounds check once and for all at the *entrance* of "flood". Since the visited node doesn't know from where it was visited, we have to give him at least the information what colour we are searching for, here I call it "farmer".

The variable "farmer" could also be global like land, m and n. On the other hand, these variables could also be passed as parameters to "flood", like "farmer". People tend to make things global, since that usually requires less typing and might run a bit faster

If you can write the cell contents (if you're using C++ strings or if you use two-dimensional arrays) then you can omit the "seen" matrix and instead overwrite the "land" matrix cells with something that doesn't appear in it otherwise, for example with '-'. This will also show that a cell has already been seen and will even be automatically tested when we test if the cell is of the colour we're currently searching for.

See Also Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.