A square grid(NxN) is given to you; Each location on the grid is either a brick (B) or its empty (_).

The total number of bricks is exactly equal to as much is required to build a “wall” in the grid. See example for clearer understanding.

That is, at the end , all bricks(B) should be placed at boundary locations.

For moving a brick from location <x,y> to <i,j> |i-x| + |j-y| fuel is used.

Each brick in the grid can be moved to any location on the boundary with equal probability. What is the expected value of the fuel required to do so? Each brick can be moved at-most once.

In the end (after moving all the bricks), the grid should look like:

 B B B B
 B _ _ B
 B _ _ B
 B B B B