2、快速传球

班级组织传球活动，男女同学随机排成m行n列队伍，第一列中的任意个男同学都可以作为传球的起点，要求最终将球传到最后一列的任意-个男同学手里，求所有能够完成任务的传球路线中的最优路线(传球次数最少的路线)的传球次数。
传球规则:
1.男同学只能将球传给男同学，不能传给女同学
2.球只能传给身边前后左右相邻的同学。
3.如果游戏不能完成，返回-1。
说明:
1.传球次数最少的路线为最优路线
2.最优路线可能不唯一，不同最优路线都为最少传球次数

> 代码

class Solution {
public:
    int lowpath(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int> dp(m, -1);
        //初始化
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                dp[i] = 0;
            }
        }
        //迭代
        for (int i = 1; i < n; i++) {
            //左右迭代
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[j][i] == 1 && dp[j] != -1) {
                    dp[j] += 1;
                }
            }
            //上下迭代
            for (int j = 0; j < m; j++) {
                int lhs, rhs;
                if (obstacleGrid[j][i] == 0) {
                    dp[j] = -1;
                    continue;
                }
                if (j - 1 < 0 || dp[j - 1] < 0) {
                    lhs = INT_MAX;
                }
                else {
                    lhs = dp[j - 1] + 1;
                }
                if (j + 1 > 0 || dp[j + 1] < 0) {
                    rhs = INT_MAX;
                }
                else {
                    rhs = dp[j + 1] + 1;
                }
                int k = min(lhs, rhs);
                if (dp[j] == -1) {
                    dp[j] = (k == INT_MAX) ? -1 : k;
                }
                else {
                    dp[j] = min(dp[j], k);
                }
            }
        }
        return dp[m - 1];
    }
};