Algorithm to remove cells of an array that are the same and connected needed please!

Posted on 2003-03-08
Medium Priority
Last Modified: 2010-04-04

I have an array[0..7,0..15] of what for the purpose of this can be assumed to be 1's and 0's.  They will be arranged in random patterns, for example:


etc and I'm going to get the location of a cell and have to identify all cells that have the same value in them and also are connected somehow to it.  For example


contains one whole group as each cell is connected to another of the same value.

Basically I'm finding groups of either 1's or 0's given a cell to start from.

I've tried the following algorithm start but run out of ideas:

make a copy of array
remove from copy array anything not same value
        remove items with no connection to any other (isolated values)
        leaves a series of groups
        identify group cell is in
        go systematically through the group marking each cell on the original array.

My problem is the "systematically" bit.. I've tried thinking of recursion and think that's the right track but I really can't write one that works.. Help anyone? please?

I'm also running on a deadline (This is about the only thing that I have left to finish on the program) so any code would be gratefully received!!


Question by:PCurd

Accepted Solution

billious earned 200 total points
ID: 8097058
I think you want to coynt the number of contiguous areas of a particular character.

This might help (untested!)

global area:

  ar_chars      : array[0..7,0..15] of char;
  ch_processed  : char;
  ch_found      : char;
  ct_found      : array[#0..#255] of byte;

procedure analyse;
  x       : integer;
  y       : integer;
  ct_size : word;

procedure mark(x,y : integer);
  if (x >= 0) and (y >= 0) and
     (x <= 15) and (y <= 15) and
     (ar_chars[x,y] = ch_found) then {correct character in valid cell ref.}
    ar_chars[x,y] := ch_processed; {this cell has been processed}
    mark(pred(x),y); {cell WEST}
    mark(succ(x),y); {cell EAST}
    mark(x,pred(y)); {cell NORTH}
    mark(x,succ(y)); {cell SOUTH}

begin {analyse}
{initialise counts}
  for ch_found := #0 to #255 do
    ct_found[ch_found] := 0; {count of AREAS of cells}
  ch_processed := 'P'; {'P' for processed - anything convenient}
  for x := 0 to 7 do
    for y := 0 to 15 do
      if ar_chars[x,y] <> ch_processed then {for UNprocessed cells}
        ch_found := ar_chars[x,y]; {save repeated calculations to access char being processed}
        ct_size := 0; {size of current area = 0}
        mark(x,y); {process this and all surrounding cells}
        {here, ct_size is the size of the current area found
         so, if you only want non-isolated cells
        if ct_size > 1 then ... }
        inc(ct_found[ch_found]); {one more area of this char found}


Author Comment

ID: 8100199
I had to make a few changes and mostly recoded "analyse" but it was extremely useful :-D

Thank you for your quick response and very helpful code!


Featured Post

[Webinar] Database Backup and Recovery

Does your company store data on premises, off site, in the cloud, or a combination of these? If you answered “yes”, you need a data backup recovery plan that fits each and every platform. Watch now as as Percona teaches us how to build agile data backup recovery plan.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
When cloud platforms entered the scene, users and companies jumped on board to take advantage of the many benefits, like the ability to work and connect with company information from various locations. What many didn't foresee was the increased risk…
Whether it be Exchange Server Crash Issues, Dirty Shutdown Errors or Failed to mount error, Stellar Phoenix Mailbox Exchange Recovery has always got your back. With the help of its easy to understand user interface and 3 simple steps recovery proced…
Suggested Courses

569 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question