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
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
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 this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (https…
This is my first video review of Microsoft Bookings, I will be doing a part two with a bit more information, but wanted to get this out to you folks.
Suggested Courses
Course of the Month7 days, 20 hours left to enroll

765 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