“This is my 38th day of participating in the First Challenge 2022. For details: First Challenge 2022”

1706. Where will the ball land

The title

A box is represented by a two-dimensional grid of size m x N. You have n balls. The top and bottom of the box were open.

Each cell in the box has a diagonal baffle that, across two corners of the cell, directs the ball to the left or right.

  • The paddle that directs the ball to the right crosses the upper left and lower right corners, denoted by 1 in the grid.
  • The paddle that directs the ball to the left crosses the upper right and lower left corners, denoted by -1 in the grid.

Put a ball at the top of each column in the box. Each ball could get stuck in the box or fall out of the bottom. If the ball gets stuck in the “V” pattern between two baffles, or is directed by a baffle to either side of the box, it will get stuck.

Return an array answer of size N, where answer[I] is the subscript of the column that fell out of the bottom after the ball was placed in the top column I, or -1 if the ball was stuck in the box.

Example 1

Input: the grid = [[,1,1 1, 1, 1], [,1,1 1, 1, 1], [1, 1, 1,1,1], [,1,1,1 1, 1], [1, 1, 1, 1, 1]] output: [1, 1, 1, 1, 1] explanation: example is shown in figure: The B0 ball starts on column 0 and eventually falls out of column 1 at the bottom of the box. The B1 ball will start on column 1 and will get stuck in the "V" shape between columns 2, 3 and 1. The b2 ball starts in column 2, and it gets stuck in the v-shape between columns 2, 3 and 0. The B3 ball starts in column 3 and gets stuck in a "V" shape between columns 2, 3 and 0. The b4 ball starts in column 4 and gets stuck in a "V" shape between columns 2, 3 and 1.Copy the code

Example 2

Input: grid = [[-1]] Output: [-1] Explanation: The ball is stuck on the left-hand side of the box.Copy the code

prompt

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] 为 1 或 - 1

Answer key

DFS

The topic is very long and the idea is very simple;

The ball entering the grid may have three states:

  • Move to the lower left of the current grid
  • Move to the lower right of the current grid
  • Stay in the current grid

After entering the next grid, the ball also has three states. So obviously we need to recurse here.

The rest will take care of itself; Find the state of the ball recursively each time;

  • If the ball currently needs to go to the lower left grid, the state of the left grid of the ball’s current grid can only be -1. If it is not -1, the ball stays in the current grid. And the left grid must not be out of bounds.
  • If the ball currently needs to go to the lower right grid, the state of the right grid of the ball’s current grid can only be 1. If it is not 1, the ball stays in the current grid. And the right grid must not be out of bounds.

Clear thinking, the idea into the code as follows:

var findBall = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const result = [];
  for (let i = 0; i < n; i++) {
    const idx = dfs(0, i);
    result[i] = idx;
  }
  return result;

  function dfs(y, x) {
    if (y === m) return x;
    if (grid[y][x] === 1) {
      if (x + 1 < n && grid[y][x + 1] = = = -1) return -1;
      if (x + 1 === n) return -1;
      return dfs(y + 1, x + 1);
    } else if (grid[y][x] === -1) {
      if (x - 1> =0 && grid[y][x - 1= = =1) return -1;
      if (x - 1= = = -1) return -1;
      return dfs(y + 1, x - 1); }}};Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section