一、题目内容
二、题目分析
机器人从左上角开始运动,每次只可以向右或者向下运动,不可以经过障碍物,到达右下角为成功。
那我们从(0,0)点开始,分别向右向下运动,如果运动的坐标超出的边界或者碰到障碍物或者坐标被访问过,就返回,如果是正常可访问的坐标,就将它放到数组中去,并且给它标记为已访问。
接下来我们需要判断,当前访问的点是否是右下角的点,如果是,就结束一切操作,否则继续向下个坐标进发。
class Solution {
boolean flag=false;
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
int m=obstacleGrid.length;
int n=obstacleGrid[0].length;
boolean [][]visited=new boolean[m][n];
List<List<Integer>> list=new ArrayList<>();
backtrack(list,0,0,obstacleGrid,visited);
return list;
}
public void backtrack(List<List<Integer>> list,int i,int j,int [][]obstacleGrid,boolean[][]visited)
{
if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1||visited[i][j])
{
return;
}
list.add(Arrays.asList(i, j));
visited[i][j]=true;
if((i==obstacleGrid.length-1)&&(j==obstacleGrid[0].length-1))
flag=true;
if(flag==false)
backtrack(list,i+1,j,obstacleGrid,visited);
if(flag==false)
backtrack(list,i,j+1,obstacleGrid,visited);
if(flag==false)
list.remove(list.size()-1);
}
}
这部分是未经优化的代码,可以看到我用了大量的额外空间去标记它的访问情况,但是其实访问过的点可以直接将它设置为1,也就是看做障碍物,这样也可以达到不重复访问的效果。
还有一点就是,我重复的使用了诸如obstacleGrid.length之类复杂的语句,可以将它们直接定义为类的属性,简化代码。
另外还有一点需要提一下,在下面这句判断中
if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1)
{
return;
}
obstacleGrid[i][j]==1这句一定要写在最后面,因为前面的语句只要有一个正确,就会直接进入底下的return,不会执行 obstacleGrid[i][j]==1。但是如果将它放在第一个,可能i,j下标越界而错误。
最后就是为什么最后要写三个if语句,而不是将这三个语句写到一个if里。因为第一个
backtrack(list,i+1,j,obstacleGrid,visited);
执行完之后,可能已经访问到最后一个点了,flag为true,可以直接退出了,但是如果写在一个if里,那么上面的程序执行完之后,还需要继续执行,显然有问题。
底下是简化后的代码:
class Solution {
boolean flag=false;
int m,n;
List<List<Integer>> list=new ArrayList<>();
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
m=obstacleGrid.length;
n=obstacleGrid[0].length;
backtrack(0,0,obstacleGrid);
return list;
}
public void backtrack(int i,int j,int [][]obstacleGrid)
{
if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1){
return;
}
list.add(Arrays.asList(i, j));
obstacleGrid[i][j]=1;
if((i==m-1)&&(j==n-1))
flag=true;
if(flag==false)
backtrack(i+1,j,obstacleGrid);
if(flag==false)
backtrack(i,j+1,obstacleGrid);
if(flag==false)
list.remove(list.size()-1);
}
}
这个题目我已经全都在原数组操作了,但是内存消耗还是很大, 可以试试用动态规划做,先判断起点到终点是否可达,再倒序求路径。
(这部分非原创)
class Solution {
public:
vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<vector<int>> res;
int rows = obstacleGrid.size();
int cols = obstacleGrid[0].size();
// 先排除边缘情况,起点和重点不可达
if (obstacleGrid[0][0] == 1 || obstacleGrid[rows-1][cols-1] ==1)
{
return res;
}
// 初始化
bool d[rows][cols];
memset(d, 0, sizeof(bool)*rows*cols);
d[0][0] = 1;
// 首列
for (int i = 1; i < rows; ++i)
{
d[i][0] = (obstacleGrid[i][0] == 0) && d[i-1][0];
}
// 首行
for (int j = 1; j < cols; ++j)
{
d[0][j] = (obstacleGrid[0][j] == 0) && d[0][j-1];
}
// 计算
for (int i = 1; i < rows; ++i)
{
for (int j = 1; j < cols; ++j)
{
// 这里把两种情况都合并在一起了
// 先判断是否为0
// 再判断上一次位置是否可达
d[i][j] = (obstacleGrid[i][j] == 0) && (d[i-1][j] || d[i][j-1]);
}
}
// 结果
// 如果不可达,直接返回空结果
if (!d[rows-1][cols-1])
{
return res;
}
// 可达,倒序计算
int i = rows-1;
int j = cols-1;
while (i > 0 || j > 0)
{
// cout << i << "," << j << endl;
res.push_back({i, j});
// 判断上一步是上方的情况是否可达
if (i > 0 && d[i-1][j])
{
--i;
}
else
{
// 因为最后是可达,所以这里必然有一个可达的, 考虑上一步是左边的情况
--j;
}
}
// 插入起点
res.push_back({0,0});
// 倒序
reverse(res.begin(), res.end());
return res;
}
};
三、感言
动态规划几天没写,怎么手生了呢? ctmd....