Wind Turbine Placement

Problem Statement

Wind Turbine Placement Problem Description A company has a contract to build a wind farm on a rectangular plot of land. The goal is to build as many wind turbines as possible. It was recently discovered that an endangered species of bird lives on the land, and the company wants every turbine to stand at a distance greater than K from every bird habitat. The map of the land is a matrix A with N rows and M columns. A bird habitat is represented by 1 and every other location by 0 . A turbine fills exactly one cell of the map, and each cell can hold at most one turbine. The distance between two cells is the sum of their horizontal and vertical differences (Manhattan distance). For example, the distance between cells A[3][2] and A[1][4] is |3 - 1| + |4 - 2| = 4 . Implement the function: int solution(vector<vector<int>> &A, int K) that, given the matrix A and the integer K , returns the maximum number of wind turbines that can be built while staying more than K away from ever