2022-08-26：用一个大小为 m x n 的二维网格 grid 表示一个箱子 你有 n 颗球。箱子的顶部和底部都是开着的。 箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角， 可以将球导

2022-08-26：用一个大小为 m x n 的二维网格 grid 表示一个箱子
你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，
可以将球导向左侧或者右侧。
将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。
如果球恰好卡在两块挡板之间的 “V” 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
返回一个大小为 n 的数组 answer ，
其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，
如果球卡在盒子里，则返回 -1。
输入：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]]。
输出：[1,-1,-1,-1,-1]。

答案2022-08-26：

这道题需要画图，才能找到解决方法。

代码用rust编写。代码如下：

fn main() {

    let mut grid: Vec<Vec<i32>> = vec![

        vec![1, 1, 1, -1, -1],

        vec![1, 1, 1, -1, -1],

        vec![-1, -1, -1, 1, 1],

        vec![1, 1, 1, 1, -1],

        vec![-1, -1, -1, -1, -1],

    ];

    let ans = find_ball(&mut grid);

    println!("ans = {:?}", ans);

}

fn find_ball(grid: &mut Vec<Vec<i32>>) -> Vec<i32> {

    let n = grid.len() as i32;

    let m = grid[0].len() as i32;

    let mut ans: Vec<i32> = vec![];

    for _ in 0..m {

        ans.push(0);

    }

    for col in 0..m {

        // (0,0)  (0,1)  (0,2)

        let mut i = 0;

        let mut j = col;

        while i < n {

            // (i,j)  左上 -> 右下的格子  grid[i][j] == 1

            // (i+1, j+1)

            // (i,j)  右上 -> 左下的格子  grid[i][j] == -1

            // (i+1, j-1)

            let jnext = j + grid[i as usize][j as usize];

            if jnext < 0

                || jnext == m

                || grid[i as usize][j as usize] != grid[i as usize][jnext as usize]

            {

                ans[col as usize] = -1;

                break;

            }

            i += 1;

            j = jnext;

        }

        if i == n {

            ans[col as usize] = j;

        }

    }

    return ans;

}

执行结果如下：

左神java代码

2022-08-26：用一个大小为 m x n 的二维网格 grid 表示一个箱子 你有 n 颗球。箱子的顶部和底部都是开着的。 箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角， 可以将球导的相关教程结束。