I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the man can move east, west, north or south of the point (no diagonal moves). Given an end point $(p,q)$ and $K$, the goal is to reach $(p,q)$ in at most $K$ steps such that the path taken maximizes the number of blocks 'visited' by the man. There is no constraint on the structure of the path taken (it can contain cycles or revisit the same block again). A block is said to be 'visited' if the man has never been to the said block before and he then goes to the block. Revisiting a 'visited' block does not increase the count of total blocks 'visited'.
Another variant of the problem is when instead of one man, there are $\ell$ men, each of whom want to reach $(p,q)$ in at most $K$ steps while maximizing the total number of blocks visited by all of them.
I thought that a simple DP algorithm would suffice to solve it but now I am suspecting that this problem is NP-hard but can't show that either. Any leads appreciated!