在給定障礙物的二維數(shù)組中求解（不新建二維數(shù)組，leetcode：時(shí)間擊敗100%用戶，內(nèi)存擊敗95.57%用戶）

class Solution {

public:

? ? int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

? ? ? ? int m = obstacleGrid.size(), n = obstacleGrid[0].size();

? ? ? ? // 對(duì)首列初始化：無障礙物:初始化為-1，最后返回結(jié)果取反即可。有障礙物：數(shù)值不變，但其后若有方格，全部初始化為0

? ? ? ? for (int i = 0; i < m; ++i) {

? ? ? ? ? ? if (obstacleGrid[i][0] == 1) {

? ? ? ? ? ? ? ? i++;

? ? ? ? ? ? ? ? while (i < m) obstacleGrid[i++][0] = 0;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? ? ? obstacleGrid[i][0] = -1;

? ? ? ? }

? ? ? ? for (int i = 0; i < n; ++i) { ? ?// 同理，對(duì)首行初始化

? ? ? ? ? ? if (obstacleGrid[0][i] == 1) {

? ? ? ? ? ? ? ? i++;

? ? ? ? ? ? ? ? while (i < n) obstacleGrid[0][i++] = 0;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? ? ? obstacleGrid[0][i] = -1;

? ? ? ? }

? ? ? ? for (int i = 1; i < m; ++i) { ? // 遍歷二維網(wǎng)格

? ? ? ? ? ? for (int j = 1; j < n; ++j) {

? ? ? ? ? ? ? ? if (obstacleGrid[i][j] == 1) continue; // 若方格是障礙物(即為1)，則跳過

? ? ? ? ? ? ? ? if (obstacleGrid[i-1][j] == 1) // 若上方方格為障礙物，則到當(dāng)前方格的路徑數(shù) = 左方方格路徑數(shù)

? ? ? ? ? ? ? ? ? ? obstacleGrid[i][j] = obstacleGrid[i][j-1];

? ? ? ? ? ? ? ? else if (obstacleGrid[i][j-1] == 1) // 同理，左方障礙物，當(dāng)前 = 上方路徑數(shù)

? ? ? ? ? ? ? ? ? ? obstacleGrid[i][j] = obstacleGrid[i-1][j];

? ? ? ? ? ? ? ? else ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 左方，上方均無障礙物，則相加

? ? ? ? ? ? ? ? ? ? obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if (obstacleGrid[m-1][n-1] == 1) return 0; // 若終點(diǎn)為障礙物，則返回0

? ? ? ? return -obstacleGrid[m-1][n-1]; // 取反即是答案

? ? }

};