Posted on

## Submission

```class Solution {
int m, n;
using ai3 = array<int, 3>;
using pii = pair<int, int>;
vector<int> dirs;
public:
int cutOffTree(vector<vector<int>>& forest) {
m = forest.size();
n = forest[0].size();
vector<ai3> heights;
heights.reserve(m * n);
dirs = {-1, 0, 1, 0, -1};

int minRow = -1;
int minCol = -1;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(forest[i][j] > 1) heights.push_back({forest[i][j], i, j});
}
}
sort(heights.begin(), heights.end());

if(heights[0][0] == 0) return -1;
if(!(heights[0][1] == 0 && heights[0][2] == 0)) heights.insert(heights.begin(), {-1, 0, 0});

// find out the shortest distance between each of these consecutive points
int ret = 0;

for(int i = 0; i < heights.size() - 1; ++i) {
auto [h1, x1, y1] = heights[i];
auto [h2, x2, y2] = heights[i+1];
queue<pii> q;
vector<vector<int>> visited(m, vector<int>(n, 0));
q.push({x1, y1});

int count = -1;
bool isFound = false;

while(!q.empty() && !isFound) {
int size = q.size();
count++;

while(size--) {
auto [x, y] = q.front();
q.pop();

if(visited[x][y]) continue;
visited[x][y] = 1;

if(x == x2 && y == y2) {
isFound = true;
break;
}

for(int j = 0; j < 4; ++j) {
int nx = x + dirs[j];
int ny = y + dirs[j+1];
if(nx < 0 || ny < 0 || nx >= m || ny >= n || forest[nx][ny] == 0 || visited[nx][ny]) continue;
q.push({nx, ny});
}
}
}
if(!isFound) return -1;
ret += count;
}

return ret;
}
};

// 2 3 4
// 0 0 5
// 8 7 6

// 4 2 3
// 0 0 1
// 7 6 5

// 1 should be ignored!
// 4->2: 1
// 2->3: 1
// 3->4: 2
// 4->5: 4
// 5->6: 1
// 6->7: 1```