C/C++ Coding problem to be solved

Solve the following coding problem.

Given a (rxc) matrix, with some cells blocked, and a maximum number of moves (k) that can be traversed is given.
Find a path that will traverse maximum number of unique unblocked cells.
Traversing back to previously visites cells are allowed, but it will be counted as a single unique cell.
You can move in left, right, top and botton except diagonally. Each traversal from one cell to another cost one move.
There can be more than one possible solution.

Create a C++ class that with take matrix's row, column number, blocked cells position and moves.
It should return the traversed path and the maximum coverage.
Time complexity should be (rxc)^3 or better.

Example:
Input: Consider below 8x8 matrix with . are unblocked cells and # are blocked cells.
Maximum moves = 25
. . . . . . . .
. . . . . . . .
# # # # # . . .
. . . # . . . .
. . . # . . . .
. . . . . # . .
. . . . . . # .
. . . . . . . .

Solution:
path = (0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (1,7), (1,6), (1,5), (2,5), (2,6), (2,7), (3,7),
(3,6), (3,5), (3,4), (4,4), (4,5), (4,6), (4,7), (5,7), (6,7), (7,7)
coverage = 25