建简单网站,网站开发 待遇怎么样,北京做建筑信息的网站,百度收录批量查询工具文章目录1. 题目2. 解题2.1 DFS2.2 动态规划1. 题目
设想有个机器人坐在一个网格的左上角#xff0c;网格 r 行 c 列。 机器人只能向下或向右移动#xff0c;但不能走到一些被禁止的网格#xff08;有障碍物#xff09;。 设计一种算法#xff0c;寻找机器人从左上角移动…
文章目录1. 题目2. 解题2.1 DFS2.2 动态规划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 {vectorvectorint path;vectorvectorint ans;int m, n;bool found false;vectorvectorint dir {{1,0},{0,1}};
public:vectorvectorint pathWithObstacles(vectorvectorint 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 {};vectorvectorbool visited(m, vectorbool(n,false));dfs(grid,0,0,visited);return ans;}void dfs(vectorvectorint grid, int i, int j, vectorvectorbool 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(x0 xm y0 yn 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:vectorvectorint pathWithObstacles(vectorvectorint 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 {};vectorvectorbool dp(m,vectorbool(n,false));//求每个位置是否可以到达for(i 0; i m; i){ //初始化第一列if(grid[i][0]1)break;//障碍物elsedp[i][0] true;}for(j 0; j n; j){ //初始化第一行if(grid[0][j]1)break;//障碍物elsedp[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 {};vectorvectorint ans(mn-1);k mn-2, i m-1, j n-1;while(i!0 || j!0){ans[k--] {i,j};if(i-10 dp[i-1][j])i--;else if(j-10 dp[i][j-1])j--;}ans[0] {0,0};return ans;}
};20 ms 8.9 MB
