Anyone knows--how to solve:

Imagine we are an electricity infrastructure company and we are building an electricity network in a new country. We want to connect all cities in the country to one electricity network. Additionally, we want to minimize the cost of building the network. The country has roads and many farms. Farm owners don't allow us to build on their ground, which means we can only build electric lines along roads and cities.

We can picture the country as a matrix where:

• 1 - is a road
• 0 - is farm or any place where we cannot build
• -1 - is a city that we want to connect to the grid

Input: int[][] of geographic map of cities, farms, and roads

Output can be any choice of:

• int[][] of geographic map of where to build the network
• unsorted list of cell coordinates of where to build the network
• unsorted list of vertices of where to build the network

Example input of roads, farms, and cities:
1 | 1 | 1 | 1 | 1 | -1
1 | 0 | 0 | 0 | 0 | 1
1 | 1 | 0 | 0 | 0 | 1
0 | -1 | 0 | -1 | 1 | -1
0 | 1 | 0 | 0 | 0 | 1
0 | 1 | 1 | 1 | 1 | 1

Example output of roads/cities where electric lines will be built:
1 | 1 | 1 | 1 | 1 | -1*
1 | 0 | 0 | 0 | 0 | 1*
1 |1 | 0 | 0 | 0 | 1*
0 | -1* | 0 | -1* | 1* | -1*
0 | 1* | 0 | 0 | 0 | 1*
0 | 1* | 1* | 1* | 1* | 1*