I am trying to create a padding method that takes the initial coordinate specified by the user, validates the character and then modifies it as desired. After that, he checks adjacent squares and repeats the process. After some research, I came across an algorithm for filling the bay even after trying (it works, but cannot satisfy my maximum array requirement of 250 by 250 characters).
My initial bay filling algorithm was as follows:
public static void fillArea (int x, int y, char original, char fill){ if (picture[y-1][x-1] != original){ return; } picture[y-1][x-1] = fill; fillArea (x-1, y, original, fill); fillArea (x+1, y, original, fill); fillArea (x, y-1, original, fill); fillArea (x, y+1, original, fill); return; }
After testing, I started using the Queue method, as described in Wikipedia, and I asked this question earlier regarding a similar problem. So far I have come up with the following code:
public static void fillArea (int x, int y, char original, char fill){ if (x != 0) x--; if (y!= 0) y--; Queue<Point> queue = new LinkedList<Point>(); if (picture[y][x] != original){ return; } queue.add(new Point(x, y)); while (!queue.isEmpty()){ Point p = queue.remove(); if (picture[py][px] == original){ picture[py][px] = fill; queue.add(new Point(px-1, py)); queue.add(new Point(p.x+1, py)); queue.add(new Point(px, py-1)); queue.add(new Point(px, p.y+1)); } } return; }
While the first, recursive method could work for smaller values, it does not work when the array becomes too large. However, the second method leads me into some kind of endless cycle, which I cannot determine due to my inexperience from the Queue. How can I either optimize the first code example for working with larger samples, or fix the second one so that it gives results? Can someone explain how to encode either of these two, or what am I doing wrong?
Thanks!
EDIT: I managed to find an infinite loop error in the second code (it was fixed), but the queue-based method does not fill the entire area. In fact, it fills less area than the recursion-based method. EDIT 2: Now it works for square arrays. How can I guarantee that it works for rectangular arrays (second method).