ZCO Spaceman Spiff and Rectangles - an extension

Spaceman Spiff

Problem link: http://www.iarcs.org.in/inoi/2013/zco2013/zco2013-2b.php

What if the spaceman could move up and left as well? Definitely, more of the paths which are not possible just moving down and right will become possible now even though they take a long time, but not all. What’s the most efficient way to figure out the answer in such a case?

Rectangles

Problem link: http://www.iarcs.org.in/inoi/2015/zco2015/zco2015-afternoon.pdf (problem 2)

What if I were to find the rectangle of largest area whose base does not lie along X axis? What’s the most efficient way?