1
class Solution {
2
 public:
3
  int util(vector<vector<int>> &grid, bool top, int i, int j) {
4
    if (top == 0 && i == grid.size() - 1) return j;
5
    if (top == 1) {
6
      if (grid[i][j] == 1) {
7
        if (j + 1 >= grid[0].size() || grid[i][j + 1] == -1) return -1;
8
        return util(grid, !top, i, j + 1);
9
      } else {
10
        if (j - 1 < 0 || grid[i][j - 1] == 1) return -1;
11
        return util(grid, !top, i, j - 1);
12
      }
13
    } else {
14
      return util(grid, !top, i + 1, j);
15
    }
16
  }
17
  vector<int> findBall(vector<vector<int>> &grid) {
18
    vector<int> ans(grid[0].size(), -1);
19
    for (int i = 0; i < grid[0].size(); i++) {
20
      ans[i] = util(grid, true, 0, i);
21
    }
22
    return ans;
23
  }
24
};