# 1706. Where does the ball meet Problem solution

Title Source: 1706. Where does the ball meet

2022.02.24 one question per day

Daily question column address: LeetCode daily problem solution is being updated ❤️💕

Today's topic is easier. After solving the problem, I'll pack my bags and go back to school tomorrow. I hope it's easy tomorrow, hehe

Today's topic is easy to understand, which is to simulate the walking path of a small ball

We can split the walking path of the small ball. From A to B in the figure, we will find that the walking of the small ball is divided into three parts

Therefore, in the first layer, we only need to count the changes of col

### Method 1: simulation method

The first is the simulation method, that is, simple simulation. You can change the col value of the ball

class Solution { public: int m, n; vector<int> findBall(vector<vector<int>> &grid) { // Counts the length and width of a given array m = grid.size(), n = grid[0].size(); // Give the result array in advance vector<int> res(n, -1); // Simulate the action route of traversing each small ball for (int i = 0; i < n; i++) { // First, define a variable to mark the position of the ball int col = i; // Traverse the corresponding position of each row for (vector<int> row: grid) { int temp = row[col]; // Update the position of the ball col += row[col]; // If the position of the ball is updated and outside the array, it proves that the ball is stuck in the frame // If the two positions of the small ball are not equal, it means that the small ball is stuck in a V if (col < 0 || col >= n || temp != row[col]) { // It proves that the ball has been stuck and can't continue to dive col = -1; break; } } // If the last coordinate of the ball is not - 1, it proves that the ball has escaped successfully, and the value in the result array is updated if (col >= 0) { res[i] = col; } } return res; } };

class Solution { int m, n; public int[] findBall(int[][] grid) { // Counts the length and width of a given array m = grid.length; n = grid[0].length; // Give the result array in advance int[] res = new int[n]; Arrays.fill(res, -1); // Simulate the action route of traversing each small ball for (int i = 0; i < n; i++) { // First, define a variable to mark the position of the ball int col = i; // Traverse the corresponding position of each row for (int[] row : grid) { int temp = row[col]; // Update the position of the ball col += row[col]; // If the position of the ball is updated and outside the array, it proves that the ball is stuck in the frame // If the two positions of the small ball are not equal, it means that the small ball is stuck in a V if (col < 0 || col >= n || temp != row[col]) { // It proves that the ball has been stuck and can't continue to dive col = -1; break; } } // If the last coordinate of the ball is not - 1, it proves that the ball has escaped successfully, and the value in the result array is updated if (col >= 0) { res[i] = col; } } return res; } }

### Method 2: DFS

The next step is DFS,

First, we need to find out when the ball gets stuck

There are four situations in total, including C, D, E and F in the picture

After removing these four cases, the ball changes its col position, and the value of row will increase by 1

The end condition is that either the ball is stuck or the value of row is greater than the value of m

Then it's simple. Let's write the code

class Solution { public: int m, n; vector<vector<int>> grid; vector<int> findBall(vector<vector<int>> &grid) { // Counts the length and width of a given array m = grid.size(), n = grid[0].size(); this->grid = grid; // Define result array vector<int> res; // Traverse the ball and perform recursive operation for (int i = 0; i < n; i++) { res.push_back(dfs(0, i)); } return res; } int dfs(int i, int j) { // Simulate the jamming of E and F if ((j == n - 1 && grid[i][j] == 1) || (j == 0 && grid[i][j] == -1)) return -1; // Simulate the situation that the ball is stuck by V-shape if (grid[i][j]!=grid[i][j+grid[i][j]]) return -1; // If it is at the bottom, just update the position of the ball (i.e. step 3) if (i == m - 1) return j + grid[i][j]; // If the meaning condition is not satisfied, it indicates that the ball is still falling, and recursion continues return dfs(i + 1, j + grid[i][j]); } };

class Solution { int m, n; int[][] grid; int[] findBall(int[][] grid) { // Counts the length and width of a given array m = grid.length; n = grid[0].length; this.grid = grid; // Define result array int[] res = new int[n]; // Traverse the ball and perform recursive operation for (int i = 0; i < n; i++) { res[i] = dfs(0, i); } return res; } int dfs(int i, int j) { // Simulate the jamming of E and F if ((j == n - 1 && grid[i][j] == 1) || (j == 0 && grid[i][j] == -1)) return -1; // Simulate the situation that the ball is stuck by V-shape if (grid[i][j] != grid[i][j + grid[i][j]]) return -1; // If it is at the bottom, just update the position of the ball (i.e. step 3) if (i == m - 1) return j + grid[i][j]; // If the meaning condition is not satisfied, it indicates that the ball is still falling, and recursion continues return dfs(i + 1, j + grid[i][j]); } }

### Method 3: dynamic programming

Finally, the method of dynamic programming

When recursing just now, we can find such a rule g r i d [ i ] [ j ] = = g r i d [ i ] [ j + g r i d [ i ] [ j ] ] grid[i][j]==grid[i][j+grid[i][j]] grid[i][j]==grid[i][j+grid[i][j]]

Our problem is to determine which channel the ball can finally fall out of

Let's change our mind

Which balls can fall out of each exit

Let's convert the formula g r i d [ i ] [ j − g r i d [ i ] [ j ] ] = = g r i d [ i ] [ j ] grid[i][j-grid[i][j]]==grid[i][j] grid[i][j−grid[i][j]]==grid[i][j]

Look up the entrance from the exit. The small ball that cannot find the entrance is the small ball (- 1) that will be stuck on the way

Direct code

class Solution { public: vector<int> findBall(vector<vector<int>> &grid) { int m, n; // Counts the length and width of a given array m = grid.size(), n = grid[0].size(); // Create a marker array. res[0] is the initial state of the ball. The default value is - 1. It cannot reach the exit by default vector<vector<int>> res(m + 1, vector<int>(n, -1)); // Give the initial value of dynamic programming // The value in the exit grid is the col where the exit is located for (int i = 0; i < n; i++) res[m][i] = i; // Perform dp for (int row = m - 1; row >= 0; row--) for (int col = 0; col < n; col++) { // If it is not in this range n, the ball has been stuck if (col - grid[row][col] < 0 || col - grid[row][col] >= n) continue; if (grid[row][col] == grid[row][col - grid[row][col]]) res[row][col - grid[row][col]] = res[row + 1][col]; } return res[0]; } };

class Solution { public int[] findBall(int[][] grid) { int m, n; // Counts the length and width of a given array m = grid.length; n = grid[0].length; // Create a marker array. res[0] is the initial state of the ball. The default value is - 1. It cannot reach the exit by default int[][] res = new int[m + 1][n]; for (int i = 0; i < m + 1; i++) for (int j = 0; j < n; j++) res[i][j] = -1; // Give the initial value of dynamic programming // The value in the exit grid is the col where the exit is located for (int i = 0; i < n; i++) res[m][i] = i; // Perform dp for (int row = m - 1; row >= 0; row--) for (int col = 0; col < n; col++) { // If it is not in this range n, the ball has been stuck if (col - grid[row][col] < 0 || col - grid[row][col] >= n) continue; if (grid[row][col] == grid[row][col - grid[row][col]]) res[row][col - grid[row][col]] = res[row + 1][col]; } return res[0]; } }

Note: I don't know if there is a better way to fill the two-dimensional array with Java (please forgive me for learning Java by yourself at the beginning), and please give me some advice