TopCoder problem "Unblur" used in TCO04 Semifinal 3 (Division I Level One)



Problem Statement

    

A simple way to blur an image is to replace each pixel with the average of it and its neighboring pixels. The value of each pixel in the blurred image is computed by adding the values of the 3x3 region centered at the corresponding pixel of the original image, and dividing by 9.

When computing the value of pixels on the border, the 3x3 region will fall partially outside of the original image. Assume that pixels outside of the original image are black.

For example, given the following original image:

the algorithm described above results in the following blurred image:

Write a method that will, given a blurred image, return the original image. The original image will contain only black and white pixels. All pixels on the top and bottom rows and left and right columns of the original image will be black. All values of the blurred image will therefore be: 0 (black), 1/9, 2/9, 3/9, 4/9, 5/9, 6/9, 7/9, 8/9, or 9/9 (white).

The blurred image will be given as a String[]. Each character in the blurred image will be a character between '0' and '9', inclusive, giving the value of that pixel multiplied by nine. For example, the blurred image above would be given as:


{ "1233321000000000123332100000000000000000000",
  "1244422233222332334343323322232112332223321",
  "1255523344343443545343434434343233432334432",
  "0033303455465775633011445546454355753457753",
  "0033303333364543533011433336333364521346542",
  "0033303455464532445343545546454355753446542",
  "0022202344342200234343434434343233432323221",
  "0011101233221100123332223322232112332211111" }

Return the original image as a String[]. For each pixel in the original image, return a '.' if it is black and '#' if it is white. For example, the original image for the example above would be returned as:

{ "...........................................",
  ".#####...........#####.....................",
  "...#...####.####.#...#.####.###..####.####.",
  "...#...#..#.#..#.#.....#..#.#..#.#....#..#.",
  "...#...#..#.####.#.....#..#.#..#.###..####.",
  "...#...#..#.#....#...#.#..#.#..#.#....#.#..",
  "...#...####.#....#####.####.###..####.#..#.",
  "..........................................." } 
 

Definition

    
Class:Unblur
Method:original
Parameters:String[]
Returns:String[]
Method signature:String[] original(String[] blurred)
(be sure your method is public)
    
 

Constraints

-blurred will contain between 1 and 50 elements, inclusive.
-Each element of blurred will have a length between 1 and 50, inclusive, and contain only characters between '0' and '9', inclusive.
-Each element of blurred will have the same length.
-blurred will be the result of blurring a black and white image.
 

Examples

0)
    
{ "1221",
  "1221",
  "1221" }
Returns: { "....",  ".##.",  "...." }

All pixels in the center two columns are adjacent to two white pixels in the source image. The remaining pixels are adjacent to only one.

1)
    
{ "00000",
  "00000",
  "00000",
  "00000" }
Returns: { ".....",  ".....",  ".....",  "....." }
A solid black image blurs to all zeros.
2)
    
{ "0011212121100",
  "0123333333210",
  "0123333333210",
  "1233333333321",
  "1233333333321",
  "1233333333321",
  "0112121212110" } 
Returns: 
{ ".............",
 "...#.#.#.#...",
 "..#.#.#.#.#..",
 ".............",
 ".#.#.#.#.#.#.",
 "..#.#.#.#.#..",
 "............." }

original:

blurred:

3)
    
{ "1233321000000000123332100000000000000000000",
  "1244422233222332334343323322232112332223321",
  "1255523344343443545343434434343233432334432",
  "0033303455465775633011445546454355753457753",
  "0033303333364543533011433336333364521346542",
  "0033303455464532445343545546454355753446542",
  "0022202344342200234343434434343233432323221",
  "0011101233221100123332223322232112332211111" } 
Returns: 
{ "...........................................",
 ".#####...........#####.....................",
 "...#...####.####.#...#.####.###..####.####.",
 "...#...#..#.#..#.#.....#..#.#..#.#....#..#.",
 "...#...#..#.####.#.....#..#.#..#.###..####.",
 "...#...#..#.#....#...#.#..#.#..#.#....#.#..",
 "...#...####.#....#####.####.###..####.#..#.",
 "..........................................." }
This is the example from the problem statement.
4)
    
{ "0000123210000",
  "0012456542100",
  "0135789875310",
  "0258988898520",
  "1479865689741",
  "2589742479852",
  "2589742479852",
  "1479865689741",
  "0258988898520",
  "0135789875310",
  "0012456542100",
  "0000123210000" }
Returns: 
{ ".............",
 ".....###.....",
 "...#######...",
 "..#########..",
 "..####.####..",
 ".####...####.",
 ".####...####.",
 "..####.####..",
 "..#########..",
 "...#######...",
 ".....###.....",
 "............." }

original:

blurred:


Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2945

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5884&pm=2945

Writer:

legakis

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Greedy, Simple Math