网站的建设与管理自考,wordpress 不显示全文,贵阳手机网站建设,域名注册美橙题目#xff1a;
设想有个机器人坐在一个网格的左上角#xff0c;网格 r 行 c 列。机器人只能向下或向右移动#xff0c;但不能走到一些被禁止的网格#xff08;有障碍物#xff09;。设计一种算法#xff0c;寻找机器人从左上角移动到右下角的路径。
示例#xff1a;…题目
设想有个机器人坐在一个网格的左上角网格 r 行 c 列。机器人只能向下或向右移动但不能走到一些被禁止的网格有障碍物。设计一种算法寻找机器人从左上角移动到右下角的路径。
示例 输入: [ [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列右下角 解题思路动态规划
1.先找到可行的路径不可达的坐标点 dp0
2.如果终点的dp不为0说明存在可达的路径
3.那么就从终点往回走找到可以到达起点的路径每走一步都要将坐标添加到res数组中
4.由于是从后往前的所以要将res进行反转 源代码如下
class Solution {
public:vectorvectorint pathWithObstacles(vectorvectorint obstacleGrid) {vectorvectorint res;if(obstacleGrid.size()0) return res;//矩阵为空直接返回空数组int mobstacleGrid.size();int nobstacleGrid[0].size();//矩阵的起点和终点不可达则返回空数组if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1) return res;int dp[m][n];//定义动态规划数组dp[0][0]1;//起点位置可达置为1//先找第一列的元素是否可达for(int i1;im;i){//不可达dp置为0if(obstacleGrid[i][0]1) dp[i][0]0;//可达则dp等于上一行的else{dp[i][0]dp[i-1][0];}}//找第一行的元素for(int i1;in;i){if(obstacleGrid[0][i]1) dp[0][i]0;else{dp[0][i]dp[0][i-1];}}//其他剩余元素for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]1) dp[i][j]0;else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}}//如果终点的dp0说明不能到达终点则返回空数组if(dp[m-1][n-1]0) return res;//以下情况是已经找到路径了只需要把路径添加到res中//从后往前找可以到达的点int im-1,jn-1;while(i!0||j!0){res.push_back({i,j});//往上走int up0;if(i0) updp[i-1][j];//往左走int left0;if(j0) leftdp[i][j-1];//哪个dp值不为0则走哪个方向if(upleft) i--;else j--;}//最后把起点添加到数组中res.push_back({0,0});//再将数组翻转就是正确顺序了reverse(res.begin(),res.end());return res;}
}; 解题思路回溯
需要注意的是要添加一个访问数组标记该坐标是否已经被访问过。详解看代码 源代码如下
class Solution {
public:bool isfindfalse;//是否已经找到路径void dfs(vectorvectorint obstacleGrid,vectorvectorint res,vectorvectorbool visited,int m,int n,int i,int j){//如果下标i和j越界//如果已经找到路径isfindtrue//如果当前坐标有障碍物//如果当前坐标已访问//遇到以上这些情况 直接返回if(i0||im||j0||jn||isfind||obstacleGrid[i][j]1||visited[i][j]) return;//当前坐标已经到达终点说明找到路径了if(im-1jn-1){isfindtrue;//isfind置为真res.push_back({i,j});//将终点添加到数组中//并返回return;}//其余正常情况每遍历一个坐标就将该坐标标记为已访问visited[i][j]true;res.push_back({i,j});//坐标添加到数组中//递归往下走dfs(obstacleGrid,res,visited,m,n,i1,j);//递归往右走dfs(obstacleGrid,res,visited,m,n,i,j1);//回溯if(!isfind) res.pop_back();}vectorvectorint pathWithObstacles(vectorvectorint obstacleGrid) {vectorvectorint res;int mobstacleGrid.size();int nobstacleGrid[0].size();if(obstacleGrid.size()0) return res;//标记当前坐标是否已经访问过初始值都为falsevectorvectorbool visited(m, vectorbool(n, false));if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1) return res;dfs(obstacleGrid,res,visited,m,n,0,0);return res;}
};
