?
Solved

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

Posted on 2003-03-08
2
Medium Priority
?
162 Views
Last Modified: 2010-04-04
Hi!

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:

0000001
1001010
1010110
1110101

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

1000000
1110000
0011000
0110000

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!!

-
Peter

0
Comment
Question by:PCurd
[X]
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
2 Comments
 
LVL 7

Accepted Solution

by:
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:

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

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

procedure mark(x,y : integer);
begin
  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.}
  begin
    inc(ct_size);
    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}
  end;
end;

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}
      begin
        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}
      end;
end;



...Bill
0
 

Author Comment

by:PCurd
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!

-
Peter
0

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