Company: cockroach labs_6sep
Difficulty: medium
Wind Turbine Placement Problem Description The effects of global warming can be seen more and more each year. That is why many countries aim to reduce greenhouse gases by creating electricity from the wind instead of from fossil fuels. Wind turbines have fewer negative effects on the environment and create less carbon dioxide. A company has a contract to build a wind farm on a rectangular area of land. The goal is to build as many turbines as possible, to make the wind farm's power capacity as high as possible. It was recently discovered that an endangered species of bird lives on the land. The area where these birds live is called a "habitat". The company wants to build the wind turbines at a distance greater than K from every bird habitat. The map of the land is given as a rectangular matrix A of integers. Bird habitats are represented as 1 and all other locations are represented as 0. A turbine will fill exactly one cell of the map and each cell can have at most one turbine. The dis