UVa 10267
From Algorithmist
Contents |
[edit] 10267 - Graphical Editor
[edit] Summary
Simulate the actions of a simple interactive graphics editor.
[edit] Explanation
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. For this, it is best to copy the current image, make the changes to the copy so you can use the old one as a reference to figure out which pixels you should color, and then copy the results back to the current image. This can be done recursively, since the images do not get too big. 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, or is not in the region to be colored, then you don't need to recurse from its neighboring pixels.
[edit] Gotcha's
- 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))
[edit] Optimizations
- 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.
[edit] Input
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
[edit] Output
one.bmp OOOOO OOOOO OAOOO OOOOO OOOOO OOOOO two.bmp JJJJJ JJZZJ JWJJJ JWJJJ JJJJJ JJJJJ
