Here is my approach :

- Calculate All pairs shortest distance using floyd Warshall for every pair of cell.

- Then **dp[subset] = optimal answer for this subset**.

- For each tyger **u** **subset** try to connect that with this subset in minimal way using pre-calculated shortest distances such that **dp[subset u] = dp[subset] + min_dis**.

- At last take sum for all subsets.

But this gives wrong answer. Please help.

Can someone tell me the approach to solve this problem ?

Have you considered that shortest paths may overlap at some squares? If they do then you will computing the cost to connect squares more than once in your final answer. For example if the min cost to connect Tyger 1 with Tyger 2 consists of connecting some square X to another square Y, which is also part of the min cost path to connect Tyger 2 with 3, then when you expand your set from 1, 2 to 1, 2, 3 via connecting 2 to 3 you will count the cost of connecting X to Y twice.

Yeah I think you are right.

Have you solved this ? shoya