m × n table plan, where every cell holds one of these values:
- 0: open land you can walk on;
- 1: a building you cannot walk through;
- 2: an obstacle you cannot walk through either.
A house is to be built on one of the open cells. You may only move up, down, left and right across open cells; the distance from the house to a building is the fewest steps from the house cell to the building cell (the last step lands on the building itself).
Pick an open cell from which every building can be reached and the total distance to all buildings is as small as possible, and return that total. If there is no such cell, return -1.plan=[[1, 0, 0, 1], [0, 2, 0, 0], [0, 0, 0, 1]] → 6
The best spot is (0, 2): the buildings are 2, 1 and 3 steps away, 6 in total. Cell (0, 1), for instance, gives 1 + 2 + 4 = 7, which is worse.
plan=[[1, 2, 0], [2, 0, 0], [0, 0, 1]] → -1
The building in the top-left corner is walled in, so no empty cell can reach it.
plan=[[0, 1, 0]] → 1
Both empty cells are right next to the building.
plan=[[1, 0, 0, 1], [0, 2, 0, 0], [0, 0, 0, 1]]
6
Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.