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代码