This was a tough nut!
Its a graph problem. Its actually a combination of 2 problems in one! I have voted it as hard and given it my recommendation.
I went through the following resources (none has the actual solution but all serve as hints) to finally come up with a solution for it:
Tested and Accepted: http://www.spoj.com/status/ROBOTGRI,chandniverma/
Time complexity in the worst case: O(n^2 + E)
where n = number of rows (or columns) in the grid
and E = number of edges in the connected graph containing the starting cell 'S'.
Space complexity: O(n^2)