Editorial: LeetCode 1706 Where Will the Ball Fall
https://leetcode.com/problems/where-will-the-ball-fall/ from Google
Thinking process:
Interesting problem. The size of the grid is less than 100, so you basically just need a DFS to go through each starting point and find the answer. The key point is how to model this problem so that you can use DFS to solve it.
For each grid, there are four edges. We can define each edge as a number, which means a ball coming into the grid from that edge. We need to know this because the ball will behave differently if it’s coming from differernt edge.
For example, if the current grid is 1, and if the ball is comming from edge 0, then it should go right next, but if it’s coming from 3 (right), then it should go down. Notice that a ball cannot go up, so the edge 2 will never be used.
Here is the code.
1class Solution {
2public:
3 int R, C;
4 int dfs(vector<vector<int>>& grid, int r, int c, int from) {
5 if (r == R) return c;
6 if (c == C or c < 0) return -1;
7 if (from == 0) {
8 if (grid[r][c] == 1) return dfs(grid, r, c+1, 1);
9 else return dfs(grid, r, c-1, 3);
10 } else if (from == 1) {
11 if (grid[r][c] == 1) return dfs(grid, r+1, c, 0);
12 else return -1;
13 } else {
14 if (grid[r][c] == 1) return -1;
15 else return dfs(grid, r+1, c, 0);
16 }
17 }
18 vector<int> findBall(vector<vector<int>>& grid) {
19 R = grid.size();
20 C = grid[0].size();
21 vector<int> ans;
22 for (int i=0; i<C; i++) {
23 auto r = dfs(grid, 0, i, 0);
24 ans.push_back(r);
25 }
26 return ans;
27 }
28};