Solved

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

Posted on 2003-03-08
Medium Priority
163 Views
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
Question by:PCurd

LVL 7

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:

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

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

-
Peter
0

## Featured Post

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
Course of the Month9 days, 21 hours left to enroll