# Searching horizontal / vertical lines in 2D arrays

This topic is 2458 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Heya,

I've got a bit of a problem that I can't figure out. I have 2D arrays of arbitrary sizes, and they contain characters like 'a', 'b', 'c' and so on. I need to break the arrays down into individual horizontal and vertical lines of the same characters, while a single character is only in one "partial array."

For example, let's concider this array:
 0 1 2 3 4 . . . 0 a a a a a 1 a 2 a a a a 3 a 4 a . . 

Now, the result I want would be something like this:

 Array 1: 0 1 2 3 4 0 a a a a a 1 2 3 4 Array 2: 0 1 2 3 4 0 1 a 2 a 3 a 4 a Array 3: 0 1 2 3 4 0 1 2 a a a 3 4 

These arrays would of course be converted into coordinate lists for smaller memory. I've tried to think through this for a while, but can't really find any practical ways to do so. Any help is appreciated.

##### Share on other sites
Loop through every row counting how many equal 'a's you have found. Remember the maximum so far and where it was. Do the same thing column by column. Now take the place where the maximum was achieved, write down the corresponding line and remove it from the data. Rinse, repeat.

This might not be very fast, but it will at least serve as a basic implementation to get you going. You can speed it up a lot by remembering the places where you found the longest rows. Also, your example doesn't allow me to tell if you are OK describing a cross as two lines, or if you would rather describe it as one column and two rows, because you don't want to repeat the intersection. In any case, there are ways to make the process fast and I am sure you'll find them.

##### Share on other sites

Loop through every row counting how many equal 'a's you have found. Remember the maximum so far and where it was. Do the same thing column by column. Now take the place where the maximum was achieved, write down the corresponding line and remove it from the data. Rinse, repeat.

This might not be very fast, but it will at least serve as a basic implementation to get you going. You can speed it up a lot by remembering the places where you found the longest rows. Also, your example doesn't allow me to tell if you are OK describing a cross as two lines, or if you would rather describe it as one column and two rows, because you don't want to repeat the intersection. In any case, there are ways to make the process fast and I am sure you'll find them.

The speed is not important since it won't be done runtime. The cross would indeed be one column and two rows (or vice versa), because a single char can only be part of a single line.

I didn't quite understand your suggestion, but it may just be my awful after-flu-stupidity and tiredness, hopefully I'll get it clear tomorrow with a bright mind.

##### Share on other sites
Something like this:
#include <iostream> bool get_longest_line(char array[5][5], int &x, int &y, int &dx, int &dy, int &length) { length = 0; for (int j=0; j<5; ++j) { int current_length = 0; for (int i=0; i<5; ++i) { current_length = array[j] == 'a' ? current_length+1 : 0; if (current_length > length) { length = current_length; x = i-length+1; y = j; dx = 1; dy = 0; } else current_length = 0; } } for (int i=0; i<5; ++i) { int current_length = 0; for (int j=0; j<5; ++j) { current_length = array[j] == 'a' ? current_length+1 : 0; if (current_length > length) { length = current_length; x = i; y = j-length+1; dx = 0; dy = 1; } } } return length > 0; } int main () { char array[5][5] = { {'a','a','a','a','a'}, {' ','a',' ',' ',' '}, {' ','a','a','a','a'}, {' ','a',' ',' ',' '}, {' ','a',' ',' ',' '} }; int x, y, dx, dy, length; while (get_longest_line(array, x, y, dx, dy, length)) { std::cout << '(' << x << ',' << y << ") d=(" << dx << ',' << dy << ')' << length << '\n'; for (int i=0; i<length; ++i) array[y+i*dy][x+i*dx] = ' '; } } 

##### Share on other sites
Gee, thanks for the code! I also got some advice from Daniweb, which will produce even distribution for horizontal and vertical segments. Thank

1. 1
2. 2
3. 3
Rutin
24
4. 4
5. 5
khawk
14

• 11
• 11
• 23
• 10
• 9
• ### Forum Statistics

• Total Topics
633651
• Total Posts
3013128
×