Cut Off Trees for Golf Event LeetCode solution in C++

1
class Solution {
2
 public:
3
#define vi vector<int>
4
#define vvi vector<vi>
5

6
  vvi forests;
7
  vvi moves;
8
  int R;
9
  int C;
10

11
  bool isValid(int x, int y) {
12
    return x >= 0 && x < R && y >= 0 && y < C;
13
  }
14

15
  int getShortestDistance(int sx, int sy, int ex, int ey) {
16
    vvi vis = vvi(R, vi(C, 0));
17
    queue<pair<int, int>> Q;
18
    Q.push({sx, sy});
19

20
    vis[sx][sy] = 1;
21

22
    int level = 0;
23

24
    while (!Q.empty()) {
25
      queue<pair<int, int>> childQ;
26

27
      while (!Q.empty()) {
28
        auto x = Q.front().first;
29
        auto y = Q.front().second;
30

31
        Q.pop();
32

33
        if (x == ex && y == ey) return level;
34

35
        for (auto ele : moves) {
36
          int nextX = x + ele[0];
37
          int nextY = y + ele[1];
38

39
          if (isValid(nextX, nextY) && !vis[nextX][nextY] && forests[nextX][nextY] > 0) {
40
            childQ.push({nextX, nextY});
41
            vis[nextX][nextY] = 1;
42
          }
43
        }
44
      }
45
      Q = childQ;
46

47
      level++;
48
    }
49

50
    return -1;
51
  }
52

53
  int cutOffTree(vector<vector<int>> &forest) {
54
    moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
55

56
    forests = forest;
57

58
    R = forest.size();
59
    C = forest[0].size();
60

61
    if (forest[0][0] == 0) return -1;
62

63
    vector<vector<int>> trees;
64
    int i = 0;
65

66
    while (i < R) {
67
      int j = 0;
68
      while (j < C) {
69
        if (forest[i][j] > 1) trees.push_back({forest[i][j], i, j});
70

71
        j++;
72
      }
73
      i++;
74
    }
75

76
    if (trees.empty()) return -1;
77

78
    sort(trees.begin(), trees.end());
79

80
    int sx = 0;
81
    int sy = 0;
82

83
    int ans = 0;
84

85
    for (auto it : trees) {
86
      int dis = getShortestDistance(sx, sy, it[1], it[2]);
87

88
      if (dis == -1) return -1;
89
      ans += dis;
90
      sx = it[1];
91
      sy = it[2];
92
    }
93

94
    return ans;
95
  }
96
};