Graph algorithm concerning colors
Hi, all.
Suppose we have a rectangle of widthw and heighth, which hasw*h square grids. At any time each grid can either be empty or be occupied by a colored square. Wheneverl squares in a series (horizontal, vertical or diagonal) have the same color, we call them "connected". Notel here is a variable. So I need an algorithm to find out all such connected squares.
I think it is a question in the graph theory field. Anyone got a hint or an idea for me? Many thanks.
[533 byte] By [
allenchuea] at [2007-10-2 16:06:26]
I think this is something like Columns, the game.
> I think it is a question in the graph theory field.> Anyone got a hint or an idea for me? Many thanks.Google for BFS-search (breadth first search).
I know breadth-first search. But I think it is used to find the minimal spanning tree of a connected graph, which is seemingly not the purpose here. So any other ideas?
> I know breadth-first search. But I think it is used
> to find the minimal spanning tree of a connected
> graph, which is seemingly not the purpose here. So
> any other ideas?
Maybe you need to Google on the subject. I'm pretty sure this can be done using BFS.
Thanks. BFS is used to traverse all vertices in a non-repetitive manner, and constructs a minimal spanning tree at the same time.
But I'm still not so clear about how to resolve my problem. Suppose BFS is used, do you mean I should start at any vertex and search for adjacent vertex that has the same color with the current one, and iterate like this? If so, I have to apply this procedure on each occupied grid. Did I go right? If not, could you be more specific?
> But I'm still not so clear about how to resolve my
> problem. Suppose BFS is used, do you mean I should
> start at any vertex and search for adjacent vertex
> that has the same color with the current one, and
> iterate like this? If so, I have to apply this
> procedure on each occupied grid. Did I go right? If
> not, could you be more specific?
Let's say this is a Grid which exists of a List of Cells.
[y]
5 (o)-(o)-(o)-(o)-(o)
|||||
4 (o)-(o)-(x)-(o)-(o)
|||||
3 (o)-(x)-(x)-(x)-(o)
|||||
2 (o)-(o)-(x)-(o)-(o)
|||||
1 (x)-(x)-(x)-(x)-(o)
12345 [x]
A Cell has (at least) the following methods:
- left(), returns the Cell on the left side of this Cell (or null if x = 1)
- right(), returns the Cell on the right side of this Cell
- up(), ...
- down(), ...
Say we want to examine all connected Cells with the x-color, starting at (1,1),
add that first Cell in a List and perform a BFS on the Grid:
List<Cell> connected = new ArrayList<Cell>();
connected.add(Grid.getCell(1, 1));
BFS(connected);
A BFS would look a bit like this:
void BFS(List<Cell> visited) {
// Get the last Cell in the List
Cell last = visited.get(visited.size()-1);
// Get all connected Cells
Cell left = last.left();
Cell right = ...
// If the left Cell is not null, if it's the same color
// as the last node, and if it's not already in your visited-
// list: add it and perform a BFS on the new visited-list.
if(left != null && last.color.equals(left.color) &&
!visited.contains(left)) {
visited.add(left);
BFS(visited);
}
// ...
}
Hope it's of help to you.
Good luck.
It's so kind of you to write down all these down.
However you seems to have misunderstood my definition for "connected", which I mean "all squares (or cells as you called) are in a horizontal, vertical, or diagonal line; while you code appears to count even twisting paths as long as all squares on such path have the same color, which is your comprehension for "connected".
Am I right?
> It's so kind of you to write down all these down.
You're welcome.
> However you seems to have misunderstood my definition
> for "connected", which I mean "all squares (or cells
> as you called) are in a horizontal, vertical, or
> diagonal line; while you code appears to count
> even twisting paths as long as all squares on such
> path have the same color, which is your comprehension
> for "connected".
>
> Am I right?
Yes, you're right. It was more a demonstration of how to do a BFS.
But this can easily be adjusted to something else. Say if you'd only like to do a horizontal BFS, you'll only have to examine the left- and right cells. As for vertical, you'll have to examine the up- and down cells, etc.
hi
I've solved this problem using the following method. It may be a bit simple, but does work.
I just iterate each cells in the rectangle (row-major or col-major, whatever) and try to search horizontal, vertical and diagonal paths with the current cell in the iteration as the start. If a path of length l is detected, it is added to a container object. Here note that there are two points that worth emphasis. First, only path starting at the current cell is counted. Second, this search only checks connected paths of length l, which is the argument. Clearly this algorithm is easy to implement.
You may think the time complexity is not optimal and even be bad. However, I've examined this and found that when applying on a 100 * 100 rectangle, this algo behaves gracefully, costing just little time. And what's more, a 100*100 rectangle is an over-estimation, which may be hardly to reach in my case.
This algorithm, however, is not BFS in my opinion. It should be a variant of depth-first search. And anyway, thanks very much for your help.
