You have a matrix, each cell containing either '$' or '.' , You can make a system of cells where each cell should contain '$' and strength of the system is |r1-r2| + |c1-c2|. You have to make a group of system such that the system strength is maximized and the absolute difference between two columns must be <= K.
Example.
. $ .
. $ .
$ . $
k = 3
In the above example you can make a group of all like below.
(1,2) (2,2) -> strength = 1
(1,2) (3,1) -> s = 3
(1,2) (3,3) -> s = 3
(2,2) (3,1) -> s = 2
(2,2) (3,3) -> s = 2
(3,1) (3,3) -> s = 2
sum = 13.
N , M <= 1000.
How to solve this problem efficiently ? Brute force will be to check for every cell with other cell, TC = N^4.