Cow Treats

The cows celebrated another banner month for record milk production and thus have each earned a special treat. They completely fill a w \times h rectangle formation awaiting their treat.

Each cow has a unique figure of merit F_{rc} (1 \le F_{rc} \le 1000000) which denotes her overall milk production performance. Farmer John thinks it is only fair to prioritize the treats handed out, rewarding the highest producing cows first. He plans to traverse the rectangular formation one row at a time, starting at the beginning of row $1$ and giving out all row $1$'s treats before he starts on row $2$ using the same method.

He has asked the cows to reorganize themselves so that the cows with better production are rewarded first. The cows, though, are not so very good at organization. They can either swap a pair of rows or swap a pair of columns of their formation. FJ has asked them to do the best they can by moving the best cow to the upper left corner (row $1$, column $1$), the next best cow to row $1$, column $2$ (if possible), and so on. Of course, the cows can not fully sort themselves, but they can do their best by following this heuristic:

• determine the order of FJ's treat awards:

• find the highest rated cow; swap rows and columns until she is at row $1$, column $1$; never move her again

• Then execute this rule until as many cows are placed as possible:

Find the next highest rated cow. Swap rows and columns (without moving any higher-rated cow) to move her to the best possible spot that is still available (e.g., row $1$, column $2$ if it's available or row $2$, column $1$ if no slots can be achieved in row $1$.

By way of example, consider this set of 3 \times 4 cows:

The cow with $99$ is clearly the highest-rated and belongs in the upper left corner. Swap rows $1$ and $2$ then swap columns $1$ and $2$ (or do it the other way around - the answer is the same):

The cow with $11$ should be rewarded as soon as possible after the highest-rated cow. She is current in slot ($3$, $4$), the last slot to be rewarded. At this point, it's too late to swap her into the first row or even the first column. Thus, she needs to move to ($2$, $2$) by swapping columns $2$ and $4$ then swapping rows $2$ and $3$:

The cow with $10$ is rewarded directly after the cow with $11$. The cow $9$ is already rewarded. The cow with $8$ is awarded just after the cow with $10$. The cow with $7$ is rewarded directly after the cow with $8$. The cow with $6$ is already rewarded. The cow with $5$ would best move to row $3$, column $2$ but the rows $1$ and $2$ are frozen as are all the columns. Thus, cows $1$, $4$ and $5$ do not move, and the second diagram above is the "best the cows can do".

Implement this algorithm for other rectangular arrays of cows.