一、題目

??設(shè)想有個(gè)機(jī)器人坐在一個(gè)網(wǎng)格的左上角，網(wǎng)格 r 行 c 列。機(jī)器人只能向下或向右移動(dòng)，但不能走到一些被禁止的網(wǎng)格（有障礙物）。設(shè)計(jì)一種算法，尋找機(jī)器人從左上角移動(dòng)到右下角的路徑。

??網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

??返回一條可行的路徑，路徑由經(jīng)過的網(wǎng)格的行號(hào)和列號(hào)組成。左上角為 0 行 0 列。如果沒有可行的路徑，返回空數(shù)組。

示例 1:

輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解釋:
輸入中標(biāo)粗的位置即為輸出表示的路徑，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）

說明：r 和 c 的值均不超過 100。

??點(diǎn)擊此處跳轉(zhuǎn)題目。

二、C# 題解

??可以使用回溯解，這里用動(dòng)態(tài)規(guī)劃好些。使用 path 記錄當(dāng)前位置是否能到達(dá)終點(diǎn)，因此從終點(diǎn)開始向起點(diǎn)方向進(jìn)行判斷，當(dāng)前 path[i, j] 的值為 obstacleGrid[i][j] == 0 && (path[i + 1, j] || path[i, j + 1])，即當(dāng)前無障礙物且后方有可到達(dá)路徑。對(duì)于邊界情況需要優(yōu)先特殊處理，以免數(shù)組越界。

public class Solution {public IList<IList<int>> PathWithObstacles(int[][] obstacleGrid) {int r = obstacleGrid.Length, c = obstacleGrid[0].Length;IList<IList<int>> ans = new List<IList<int>>();bool[,] path = new bool[r, c]; // 記錄可到達(dá)路徑if (obstacleGrid[r - 1][c - 1] == 1) return ans; // 如果終點(diǎn)有障礙物，直接返回空/* 動(dòng)態(tài)規(guī)劃求解可到達(dá)路徑 */path[r - 1, c - 1] = true;// 最右方邊界判斷for (int j = c - 2; j >= 0; j--)if (path[r - 1, j + 1] && obstacleGrid[r - 1][j] == 0)path[r - 1, j] = true;// 最下方邊界判斷for (int i = r - 2; i >= 0; i--)if (path[i + 1, c - 1] && obstacleGrid[i][c - 1] == 0)path[i, c - 1] = true;// 中間判斷for (int i = r - 2; i >= 0; i--)for (int j = c - 2; j >= 0; j--)if (obstacleGrid[i][j] == 0 && (path[i + 1, j] || path[i, j + 1]))path[i, j] = true;if (!path[0, 0]) return ans; // 如果起點(diǎn)沒有可到達(dá)路徑，返回空/* 求解一條可到達(dá)路徑 */int x = 0, y = 0;while (x != r - 1 || y != c - 1) {ans.Add(new List<int> { x, y });      // 添加路徑if (y + 1 < c && path[x, y + 1]) y++; // 優(yōu)先向右走else x++;                             // 右方堵住則向下走}ans.Add(new List<int> { r - 1, c - 1 });  // 添加終點(diǎn)return ans;}
}

• 時(shí)間：132 ms，擊敗 100.00% 使用 C# 的用戶
• 內(nèi)存：42.62 MB，擊敗 100.00% 使用 C# 的用戶