410561: GYM104049 M Knight in Shining Armor 2

Note that this is problem is a harder version of Knight in Shining Armor 1. There are significant differences between the two problems, so please read both carefully.

Charles is a chess prodigy, but his parents are worried that he spends too much time indoors. So, they have decided to create an exercise for him that will allow him to train his chess skills while also getting some vitamin D. Charles's parents have drawn an $$$N \times N$$$ chess board using chalk and provided Charles with a giant knight chess piece made out of tungsten. To keep him busy for a while, his parents tell him to place the knight on any square of the board he likes and then repeatedly make knight moves until the knight ends up back on the square it started. Charles is a really indecisive chess player, so at each step, he will choose uniformly randomly from the legal moves available for his knight (note that there will always be at least one legal move, and that Charles will never move the knight off of the board).

To incentivize his learning and exercise, Charles's parents have decided to reward him for each knight move that he makes. When he moves the knight to the square $$$(i, j)$$$ ($$$i$$$-th row from the top, $$$j$$$-th column from the left), he will earn $$$d_{ij}$$$ gold nuggets. Note that he will earn this reward every single time his knight lands on square $$$(i, j)$$$, not just the first time.

Charles wants to earn as many gold nuggets as possible, so he would like to choose the starting square that gives him the highest likelihood of earning the most nuggets. However, he yet again faces the dilemma that he is super indecisive. Because of this, he asks you to calculate the expected number of nuggets he will collect if he chooses his starting position uniformly randomly.

The first line of input will consist of a single integer $$$N\ (8 \leq N \leq 1000)$$$ denoting the size of the chess board. The next $$$N$$$ lines of the input will consist of an $$$N \times N$$$ grid of positive integers representing the $$$d_{ij}\ (1 \leq d_{ij} \leq 100)$$$ in row-major order.

Your output should consist of a single floating point number, the expected number of nuggets that Charles will collect if he chooses of of the starting squares of the chess board uniformly randomly and then performs repeated knight moves until reaching that starting square again. Your answer will be considered correct if it has absolute error less than or equal to $$$10^{-9}$$$.

8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

75.25

8
1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1

112.875