22220_DensityCenter

A peg board is drilled with a square matrix of holes, into which pegs might be inserted. The dimension of a peg board is the number of holes in a row or column, and is always a positive power of 2; i.e. 2ⁿ for some n ≥ 0. The density of a peg board is the number of holes containing pegs.

The density center of a peg board is a hole coordinate on the board defined recursively:

• If the dimension is 2⁰, the density center is its one and only coordinate.

• If the dimension is 2ⁿ where n > 0, the density center is the density center of the quadrant (upper left, upper right, lower left, or lower right) having the highest density. If there is a tie for highest density, the priority order (from highest to lowest) is (upper left, upper right, lower left, lower right).

Write a program that inputs a peg board and finds its density center.

The first line of input contains the dimension of the peg board, which is 2ⁿ for some n ≥ 0. The remaining 2ⁿ lines represent the peg board, with each line containing 2ⁿ characters. A blank character represents an empty hole and a non-blank character (e.g. o) represents a hole containing a peg.

Output the peg board as it appears in the input, except the coordinate of the density center, which should be marked with the character X.

16
  o oo     o  o
o     o   oo  o
 o   o ooo o  o
   o   oo    o
o        o  o  
 o          o o
o     o      ooo
o  o      o   oo
   o  oo  o  o
oo  oooooo  o o
o   oo oo  o ooo
o oooo    o oo
o ooo  oo  oo  o
o   o oo  o   oo
oooo    o oo   o
o      o    o  

  o oo     o  o
o     o   oo  o
 o   o ooo o  o
   o   oo    o
o        o  o  
 o          o o
o     o      ooo
o  o      o   oo
   o  oo  o  o
oo  oooooo  o o
o   Xo oo  o ooo
o oooo    o oo
o ooo  oo  oo  o
o   o oo  o   oo
oooo    o oo   o
o      o    o