This is a pretty common problem: http://www.spoj.com/problems/CLEANRBT/

The common solution to this is finding shortest paths among all dirty tiles, and then doing a TSP on these.

I thought about another method, actually before the above even came to my head. This is much more simpler, though takes way way more space as well as time from the first approach. However, it still fits in with the requirements of the problem, hence, I went ahead and implemented it, for the sake of it: https://ideone.com/JXlzZY

It's passing all the given test cases, as well as some which I tried myself. But I keep getting a WA on submission. Any help on this would be much appreciated.

My algo would seem pretty straight-forward from the code I posted above, but I am still going ahead to outline the particulars: I maintain a dp table corresponding to the room, and a bitmask for every such tile. So dp[i][j][mask] would have the value of reducing mask to (1<<numberOfDirtyTiles — 1), with my source as (i, j).