用一个大小为 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]。
这道题需要画图，才能找到解决方法。
代码用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;
}执行结果如下：
