leetcode_063 Unique Paths II

題意分析：此題與Unique Path是一樣的，隻是要單獨考慮障礙物對整個棋盤的影響。

解題思路：

                           增加一個判斷條件，如果有障礙物，此格填0，表示0個路徑。

                           初始條件受障礙物影響如下：

                           1）假設整個棋盤隻有一行，那麼在第i個位置上設定一個障礙物後，說明位置i到最後一個格子這些

                                 路都沒法走；

                           2）如果整個棋盤隻有一列，那麼在第i個位置上的障礙物，也會影響從第i位置往後的路；

                           綜上，在初始條件中，如果一旦遇到障礙物，障礙物後面所有的格子的走法都是0。

                          方法一：動态規劃實作

                           定義二維數組A[i][j]；

                           對于隻有一列或隻有一行的特殊情況處理。即隻有存在障礙物，則路徑為0，否則為1；

                           對于非一行和非一列的情況處理具體如下：

                           初始化A[i][j]中的第一列和第一行，具體為存在障礙物，則之後的路徑全為0。否則為1；

                           遞推公式為為 A[i][j] = (obstacleGrid[i-1][j] == 1 ? 0 : A[i-1][j]) + (obstacleGrid[i][j-1] == 1 ? 0 : A[i][j-1])；

                           最後傳回A[m-1][n-1]即可。

                           方法二：動态規劃 + 滾動數組實作

                           定義滾動數組A[m+1]；

                           初始化，原則：當某一列存在障礙物，則此時對應的A[i]值為0，否則此值A[i]值為1；

                           遞推公式為 A[j+1] = (obstacleGrid[i][j] == 1 ? 0 : A[j] + A[j+1]；

                           最後傳回A[m]即可。

class Solution
{
	public:
		// 方法一實作：動态規劃 
		int uniquePathsWithObstacles(vector< vector<int> > &obstacleGrid) 
		{
			int m = obstacleGrid.size();
			int n = obstacleGrid[0].size();
			// 處理隻有一行，或隻有一列的情況 
			if (m == 1 || n == 1)
			{
				bool hasObstacle = false;
				for (int i = 0; i < m; i++)
				{
					for (int j = 0; j < n; j++)
					{
						if (obstacleGrid[i][j] == 1)
						{
							hasObstacle = true;
							break;
						}
					}
				}
				if (hasObstacle)
					return 0;
				else
					return 1; 
			}
			// 處理非一行也非一列的情況 
			vector< vector<int> > temp(m, vector<int>(n));
			if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
				return 0;
			temp[0][0] = 1;
			// 初始化第一列 
			for (int i = 1; i < m; i++)
			{
				if (obstacleGrid[i][0] == 1)
					temp[i][0] = 0;
				else
					temp[i][0] = temp[i - 1][0];
			}
			// 初始化第一行 
			for (int j = 1; j < n; j++)
			{
				if (obstacleGrid[0][j] == 1)
					temp[0][j] = 0;
				else
					temp[0][j] = temp[0][j - 1];
			}
			// 進行中間部分 
			for (int i = 1; i < m; i++)
			{
				for (int j = 1; j < n; j++)
				{
					temp[i][j] = (obstacleGrid[i - 1][j] == 1 ? 0 : temp[i - 1][j]) + (obstacleGrid[i][j - 1] == 1 ? 0 : temp[i][j - 1]);
				}
			}
			// 傳回最終結果 
			return temp[m - 1][n - 1];
		} 
		
		// 方法二實作：動态規劃 + 滾動數組 
		int uniquePathsWithObstacles2(vector< vector<int> > &obstacleGrid)
		{
			if (obstacleGrid.empty() || obstacleGrid[0].empty())
				return 0;
			int *temp = new int[obstacleGrid[0].size() + 1];
			temp[0] = 0;
			if (obstacleGrid[0][0])
				return 0;
			else
				temp[1] = 1;
			// 初始化處理 
			for (int i = 1; i < obstacleGrid[0].size(); i++)
			{
				if (obstacleGrid[0][i])
					temp[i + 1] = 0;
				else
					temp[i + 1] = temp[i]; 
			}
			// 中間部分處理 
			for (int i = 1; i < obstacleGrid.size(); i++)
			{
				for (int j = 0; j < obstacleGrid[0].size(); j++)
				{
					if (obstacleGrid[i][j])
						temp[j + 1] = 0;
					else
						temp[j + 1] += temp[j];
				}
			}
			// 最終傳回值 
			return temp[obstacleGrid[0].size()]; 
		}
};