程序员面试金典 – 面试题 08.02. 迷路的机器人（DFS/动态规划）网络Michael是个半路程序员-

1. 题目

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。
机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。
设计一种算法，寻找机器人从左上角移动到右下角的路径。

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

返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。

示例 1: 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: [[0,0],[0,1],[0,2],[1,2],[2,2]] 解释:  输入中标粗的位置即为输出表示的路径，即 0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角） 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/robot-in-a-grid-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 DFS

一开始 34/36个通过测试

• 修改，把visited过的地方回溯的时候别改回去，因为不通，所以后面也别走了

class Solution {  vector<vector<int>> path;     vector<vector<int>> ans; int m, n; bool found = false;  vector<vector<int>> dir = {{1,0},{0,1}}; public:     vector<vector<int>> pathWithObstacles(vector<vector<int>>& grid) { if(grid.empty() || grid[0].empty()) return {};      m = grid.size(), n = grid[0].size(); if(grid[0][0]==1 || grid[m-1][n-1]==1) return {};      vector<vector<bool>> visited(m, vector<bool>(n,false)); dfs(grid,0,0,visited); return ans; } void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>> & visited) { if(found) return; if(i == m-1 && j == n-1) {       path.push_back({i,j});             ans = path;       found = true; return; }      visited[i][j] = true;      path.push_back({i,j}); int x, y; for(int k = 0; k < 2; ++k) {       x = i + dir[k][0];       y = j + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==0 && !visited[x][y]) dfs(grid,x,y,visited); } // visited[i][j] = false;//不注释会超时      path.pop_back(); } }; 

28 ms 10.4 MB

2.2 动态规划

• dp[i][j] 表示机器人能否到达该处
• 能到达终点，从终点肯定能随便走一条路回去

class Solution { public:     vector<vector<int>> pathWithObstacles(vector<vector<int>>& grid) { if(grid.empty() || grid[0].empty()) return {}; int m = grid.size(), n = grid[0].size(), i, j, k; if(grid[0][0]==1 || grid[m-1][n-1]==1) return {};      vector<vector<bool>> dp(m,vector<bool>(n,false));//求每个位置是否可以到达 for(i = 0; i < m; ++i) { //初始化第一列 if(grid[i][0]==1) break;//障碍物 else        dp[i][0] = true; } for(j = 0; j < n; ++j) { //初始化第一行 if(grid[0][j]==1) break;//障碍物 else        dp[0][j] = true; } for(i = 1; i < m; i++) { for(j = 1; j < n; j++) { if(grid[i][j]==0)//不是障碍物         dp[i][j] = (dp[i-1][j] || dp[i][j-1]); } } if(dp[m-1][n-1]==false)//到不了终点 return {};      vector<vector<int>> ans(m+n-1);      k = m+n-2, i = m-1, j = n-1; while(i!=0 || j!=0) {       ans[k--] = {i,j}; if(i-1>=0 && dp[i-1][j])        i--; else if(j-1>=0 && dp[i][j-1])        j--; }         ans[0] = {0,0}; return ans; } }; 

20 ms 8.9 MB