1. 概述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

2. 解题

<?php
class Solution {

    public $way = [];

    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    public function uniquePathsWithObstacles($obstacleGrid) {
        if (!$obstacleGrid) {
            return 0;
        }

        $n = count($obstacleGrid);
        $m = count($obstacleGrid[0]);

        $this->dp($n, $m, $obstacleGrid, [0, 0]);
        return count($this->way);
    }

    private function dp ($n, $m, $obstacleGrid, $last, $way = []) {
        if ($last == [$n - 1, $m - 1]) {
            $this->way[] = $way;
            return;
        }

        if (isset($obstacleGrid[$last[0]][$last[1] + 1]) && ($obstacleGrid[$last[0]][$last[1] + 1] == 0)) {    // 右
            $way[] = 'r';
            $this->dp($n, $m, $obstacleGrid, [$last[0], $last[1] + 1], $way);
            array_pop($way);
        }

        if (isset($obstacleGrid[$last[0] + 1][$last[1]]) && ($obstacleGrid[$last[0] + 1][$last[1]] == 0)) {    // 下
            $way[] = 'd';
            $this->dp($n, $m, $obstacleGrid, [$last[0] + 1, $last[1]], $way);
            array_pop($way);
        }
    }
}
$obstacleGrid = [
    [0,0,0],
    [0,1,0],
    [0,0,0],
];
$cls = new Solution();
$r = $cls->uniquePathsWithObstacles($obstacleGrid);
echo $r;

array_walk($cls->way, function (&$v){
    $v = implode(',', $v);
});
print_r($cls->way);