there is a problem I have been thinking on for a while but cannot find efficient algorithm for. it is similar to this problem. I have a 2D grid, some cells with 1, other cells are 0. now I need to find all 0 cells that have no more than distance of K from ALL other 1 cells. so how many eligible cell would be? I know brute force, which for every single ZERO cell check with all other 1 cell. if n^2 /2 are 0 and n^2/2 are one, then time complexity would be O(n^4). but it is not best algorithm (it's not HW or project just an ACM question I cannot solve )
0 0 0 1
0 0 0 0
0 0 1 0
0 0 0 0
if K =2 then
0 0 X 1
0 0 X X
0 0 1 X
0 0 0 0