今天开始每天打卡了！

 

 题目如上

一开始也没啥好思路，就是想着暴力解，遍历一下 每个小球的下落路径就行，区分一下情况。

后来还是看了题解再做

觉得dfs是不错的方法，采用了递归的方式

首先要区分清楚不同的情况，找到递归的出口

然后再找到递归关系即可了。

以后这种思路要有的。

class Solution {
private:
    int m,n;
public:
    
    vector<int> findBall(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        vector<int> res;
        for(int i=0;i<n;i++){
            res.push_back(dfs(grid,0,i));
        }
        return res;
    }
    int dfs(vector<vector<int>>& v, int i, int j){
        if(j == n - 1 && v[i][j] == 1 || j == 0 && v[i][j] == -1)return -1;
        if(v[i][j] != v[i][j + v[i][j]])return -1;
        if(i==m-1)return j+v[i][j];
        return dfs(v,i+1,j+v[i][j]);
    }
};