Where Will the Ball Fall
给一个2d数组, 里面1是对角线, -1是反对角线, 从每个column上往下放小球, 求小球落到哪里.
这个题里已经给出了什么时候小球不能落下的情况, 一个是碰壁, 一个是相邻的cell互为1和-1. 排除然后做dfs就可以了. 也不需要memo就能过.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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; } } } |