The quality of living in each particular block has been ranked by a distinct number, called quality rank, between 1 and R*C, where 1 is the best and R*C is the worst.
The city planning department wishes to identify a rectangular set of blocks with dimensions H from north to south and W from west to east, such that the median quality rank among all blocks in the rectangle is the best. H and W are odd numbers not exceeding R and C respectively. The median quality rank among an odd number of quality ranks is defined to be the quality rank m in the set such that the number of quality ranks better than m equals the number of quality ranks worse than m.
You are to implement a procedure rectangle(R,C,H,W,Q) where R and C represent the total size of the city, H and W represent the dimensions of the set of blocks, and Q is an array such that Q[a][b] is the quality rank for the block labeled a from north to south and b from west to east.
Your implementation of rectangle must return a number: the best (numerically smallest) possible median quality rank of an H by W rectangle of blocks.
Each test run will only call rectangle once.
R=5, C=5, H=3, W=3,
Q= 5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
For this example,
the best (numerically smallest) median quality rank of 9 is achieved
by the middle-right rectangle of Q shown in bold.
That is,
rectangle(R,C,H,W,Q)=9
R=2, C=6, H=1, W=5,
Q= 6 1 2 11 7 5
9 3 4 10 12 8
For this example the correct answer is 5.