Where Will the Ball Fall
给一个2d数组, 里面1是对角线, -1是反对角线, 从每个column上往下放小球, 求小球落到哪里.
这个题里已经给出了什么时候小球不能落下的情况, 一个是碰壁, 一个是相邻的cell互为1和-1. 排除然后做dfs就可以了. 也不需要memo就能过.
class Solution {
public int[] findBall(int[][] grid) {
int m = grid[0].length;
int[] res = new int[m];
for(int i = 0; i < m; i++){
res[i] = dfs(grid,0,i);
}
return res;
}
private int dfs(int[][] g, int r, int c){
if(r < 0 || r >= g.length || c < 0 || c >= g[0].length)
return -1;
if(g[r][c] == 1){
if(c + 1 < g[0].length && g[r][c + 1] == 1){
if(r + 1 == g.length)
return c + 1;
else
return dfs(g, r + 1, c + 1);
}
else
return -1;
}else{
if(c - 1 >= 0 && g[r][c - 1] == -1){
if(r + 1 == g.length)
return c - 1;
else
return dfs(g, r + 1, c - 1);
}
else
return -1;
}
}
}