# 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.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.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.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.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.size();
// Create a marker array. res 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;
}
};
```
```class Solution {
public int[] findBall(int[][] grid) {
int m, n;
// Counts the length and width of a given array
m = grid.length;
n = grid.length;
// Create a marker array. res 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;
}
}
```

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

Added by fredcool on Thu, 24 Feb 2022 12:28:42 +0200