UVa 10267

From Algorithmist
Jump to navigation Jump to search

10267 - Graphical Editor[edit]

Summary[edit]

Simulate the actions of a simple interactive graphics editor.

Explanation[edit]

Implement each command exactly according to the specifications and ignore any lines that do not represent a command; that is, those lines without either I, C, L, V, H, K, F, S, or X as their first character. When the problem setter says "in case of other errors, the program behavior is unpredictable", he means that you can assume there will be no other types of errors in the input other than those for which an appropriate response is specified.

The hardest part of this problem is implementing the F (fill) command. Here is a simple working algorithm :

fillContiguous(x, y, newColor, oldColor)

 if (newColor = oldColor) 
   then return;
 if (picture[x][y] = oldColor)
   then
      picture[x][y] <- newColor;
      foreach adjacent pixel
         fillContiguous(nextPixel.x, nextPixel.y, newColor, oldColor);

The simplest way of doing This can be done recursively, since the images do not get too big. Before starting a recursion, assert that oldColor != newColor. Start from the pixel specified in the command, and spread out in all four directions, and from those pixels, spread out in four directions. If a pixel has already been colored then it is not anymore in the region to be colored , if a pixel is not in the region to be colored, then you don't need to recurse from its neighboring pixels.

Gotcha's[edit]

  • For the V command, Y1 does not have to be less than Y2.
  • For the H command, X1 does not have to be less than X2.
  • The indices given in all commands are 1-based. (i.e. (1, 1) is the upper left corner, not (0, 0))
  • Depending on your implementation of the fill function (F), if newColor == oldColor then an infinite loop might occur!

Optimizations[edit]

  • Some people have found a way to implement the F (fill) command iteratively. This is probably an optimization since it avoids the overhead of recursion and the danger of stack overflow. Note however that there are 250*250 < 10000 pixels therefore we can assume that there is no risk for a stack overflow.

Input[edit]

I 5 6
L 2 3 A
S one.bmp
G 2 3 J
F 3 3 J
V 2 3 4 W
H 3 4 2 Z
S two.bmp
X

Output[edit]

one.bmp
OOOOO
OOOOO
OAOOO
OOOOO
OOOOO
OOOOO
two.bmp
JJJJJ
JJZZJ
JWJJJ
JWJJJ
JJJJJ
JJJJJ