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;
        } 
    }
}